% THIS IS SIGPROC-SP.TEX - VERSION 3.1
% WORKS WITH V3.2SP OF ACM_PROC_ARTICLE-SP.CLS
% APRIL 2009
%
% It is an example file showing how to use the 'acm_proc_article-sp.cls' V3.2SP
% LaTeX2e document class file for Conference Proceedings submissions.
% ----------------------------------------------------------------------------------------------------------------
% This .tex file (and associated .cls V3.2SP) *DOES NOT* produce:
%       1) The Permission Statement
%       2) The Conference (location) Info information
%       3) The Copyright Line with ACM data
%       4) Page numbering
% ---------------------------------------------------------------------------------------------------------------
% It is an example which *does* use the .bib file (from which the .bbl file
% is produced).
% REMEMBER HOWEVER: After having produced the .bbl file,
% and prior to final submission,
% you need to 'insert'  your .bbl file into your source .tex file so as to provide
% ONE 'self-contained' source file.
%
% Questions regarding SIGS should be sent to
% Adrienne Griscti ---> griscti@acm.org
%
% Questions/suggestions regarding the guidelines, .tex and .cls files, etc. to
% Gerald Murray ---> murray@hq.acm.org
%
% For tracking purposes - this is V3.1SP - APRIL 2009

\documentclass{acm_proc_article-sp}
\usepackage{mathtools}
\usepackage{changepage}
\newtheorem{obs}{Observation}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newdef{definition}{Definition}
\begin{document}

\title{Different Dense Bicluster Editing Problems}
\subtitle{[Extended Abstract]
\titlenote{}}
%
% You need the command \numberofauthors to handle the 'placement
% and alignment' of the authors beneath the title.
%
% For aesthetic reasons, we recommend 'three authors at a time'
% i.e. three 'name/affiliation blocks' be placed beneath the title.
%
% NOTE: You are NOT restricted in how many 'rows' of
% "name/affiliations" may appear. We just ask that you restrict
% the number of 'columns' to three.
%
% Because of the available 'opening page real-estate'
% we ask you to refrain from putting more than six authors
% (two rows with three columns) beneath the article title.
% More than six makes the first-page appear very cluttered indeed.
%
% Use the \alignauthor commands to handle the names
% and affiliations for an 'aesthetic maximum' of six authors.
% Add names, affiliations, addresses for
% the seventh etc. author(s) as the argument for the
% \additionalauthors command.
% These 'additional authors' will be output/set for you
% without further effort on your part as the last section in
% the body of your article BEFORE References or any Appendices.

\numberofauthors{3} %  in this sample file, there are a *total*
% of EIGHT authors. SIX appear on the 'first-page' (for formatting
% reasons) and the remaining two appear in the \additionalauthors section.
%

% There's nothing stopping you putting the seventh, eighth, etc.
% author on the opening page (as the 'third row') but we ask,
% for aesthetic reasons that you place these 'additional authors'
% in the \additional authors block, viz.
\author{
\alignauthor
Jan Baumbach\\
       \affaddr{?? Jan, your affiliation??}\\
       \affaddr{??}\\
       \affaddr{??}\\
       \email{??}
% 3rd. author
\alignauthor 
Jiong Guo \\
       \affaddr{Cluster of Excellence}\\
       \affaddr{Campus E1 7}\\
       \affaddr{66123 Saarbr{\"u}cken}\\
       \email{jguo@mmci-uni.saarland.de}       
\alignauthor
Peng Sun\\
       \affaddr{Max Planck Institute for Informatics}\\
       \affaddr{Campus E1 4}\\
       \affaddr{66123 Saarbr{\"u}cken}\\
       \email{psun@mpi-inf.mpg.de}
       }
\additionalauthors{}
% Just remember to make sure that the TOTAL number of authors
% is the number that will appear on the first page PLUS the
% number that will appear in the \additionalauthors section.

\maketitle
\begin{abstract}
Given a density measure $\Pi$, an undirected graph $G$ and a nonnegative integer $k$, a $\Pi$-CLUSTER EDITING problem is to check whether $G$ can be modified into a graph where all connected components are $\Pi$-cliques, by at most $k$ edge modifications. Previous studies have reported the complexity and fixed-parameter tractability of $\Pi$-CLUSTER EDITING based on several different density measures. However, whether these conclusions hold on bipartite graphs is yet to be examined. Here in this study, we focus on three different density measures on bipartite graphs: (1) having at most $s$ missing edges for each vertex ($s$-biplex), (2) having average degree at least $|V| -s$ (average-$s$-biplex), and (3) having at most $s$ missing edges within a single disjoint component ($s$-defective bicliques). First, the NP-completeness of the three problems is discussed and afterwards we show all these problems are fixed-parameter tractable with respect to the parameter $(s,k)$.
\end{abstract}



\terms{Theory}

\keywords{BICLUSTER EDITING, Parameterized complexity, Data reduction, Forbidden subgraph characterization, NP-hardness} % NOT required for Proceedings

\section{Introduction}
Graph-based data clustering methodologies have been of great importance in the scientific analyses of the real-world data, ranging from biological to social network data. In most scenarios, data entities are modeled as vertices and a certain function is defined to quantify ``relationship" between two vertices (e.g. similarities). Thresholds specified by systems or users are then used to model the edges of the graph. The clustering problem is usually defined mathematically as a ``partition" of the whole vertex set into different dense subsets, so-called \textit{clusters}, such that there are as few edges as possible between different clusters and as few missing edges as possible within clusters. The problem could also be viewed from the graph modification angle, i.e., to modify the graph by edge insertions or deletions into a $\Pi$-cluster graph, the so-called $\Pi$-CLUSTER EDITING problems. Here, a graph is a $\Pi$-cluster graph, if each of its connected components satisfies $\Pi$, where $\Pi$ is a certain density measure.

The most famous problem among the $\Pi$-CLUSTER EDITING problems is CLUSTER EDITING, where $\Pi$ is ``being a clique". CLUSTER EDITING problem has been extensively studied and proved as NP-complete among the earliest NP-complete problems \cite{Shamir,Bansal}. Successful applications of the algorithms for CLUSTER EDITING could be found in the field of computational biology \cite{Jan} and machine learning \cite{Bansal}. Moreover, from the perspective of parameterized complexity and approximability, several previous studies of CLUSTER EDITING have been reported. CLUSTER EDITING is proved to be solved in $O(1.83^k+|E|)$ time \cite{Bocker} and several different data reduction schemes have been studied and reported \cite{Cao, Chen, Langston, Jiong}. Furthermore, the current best approximation factor on CLUSTER EDITING is 2.5 \cite{Ailon,Zuylen}. In computational biology, a number of applicable heuristic algorithms have also been designed \cite{Rahmann,Jan2}.

However, in some real-world applications, ``being a clique" is increasingly criticized as over-restrictive \cite{Seidman}. Thus some relaxed models might be more advantageous in a variety of different application scenarios[]. Theoretical studies have also been conducted on relaxed versions of CLUSTER EDITING. Guo \textit{et al.} studied $s$-PLEX EDITING from the angle of parameterized complexity. In another study, they extended their research further to several other relaxed models: $s$-defective cliques, average-$s$-plexes and $\mu$-cliques [], proving the NP-completeness and discussing the fixed-parameter tractability of the problems.

In some real-world scenarios which data contains information in more than one dimension, the standard clustering model is so powerful. For instance, the microarray data analysis requires a simultaneous clustering on rows (genes) and columns (conditions) to find consistent behaviors for genes under a certain number of conditions. The traditional clustering model is not feasible for such scenarios, where data from different sources must be clustered together simultaneously. The concept of ``biclustering" was thus introduced by Cheng and Church for the first time[]. Note that biclustering problems can be easily modeled as clustering problems based on bipartite graphs by forming similarities between two different sets of vertices, described as follows:

\begin{adjustwidth}{1cm}{1cm}
BICLUSTER EDITING\\
\textbf{Input:} A bipartite graph $G=(U,V,E)$ and an integer $k>0$\\
\textbf{Question:} Can $G$ be converted into a \textit{bicluster graph} where every connected component is a biclique, by at most $k$ edge insertions and deletions?
\end{adjustwidth}

A biclique is a bipartite graph with all possible edges. Though not so extensively studied as CLUSTER EDITING, several theoretical conclusions of bicluster editing have been published, both in terms of parameterized tractability[] and approximation results[]. Applications other than microarray data analysis can be found mostly in the computational biology field, for instance, biomedical data analysis[my paper], drug repositioning[], etc.. Similarly, by relaxing the criteria of ``biclique" in different directions, $\Pi$-BICLUSTER EDITING can be yielded.

\begin{adjustwidth}{1cm}{1cm}
$\Pi$-BICLUSTER EDITING\\
\textbf{Input:} A bipartite graph $G=(U,V,E)$ and an integer $k>0$\\
\textbf{Question:} Can $G$ be converted into a $\Pi$-\textit{bicluster graph}, where every connected component is a $\Pi$-biclique, by at most $k$ edge insertions and deletions?
\end{adjustwidth}

Here in our study, we focus on the 3 cases of $\Pi$-BICLUSTER EDITING (three different density measure $\Pi$s):(1) $s$-biplex, (2) average-$s$-biplex and (3) $s$-defective biclique.

\section{Problem Definitions and Results}
An undirected graph $G = (U,V,E) $, where $U$ and $V$ are two sets of vertices and $E$ is the set of edges, is a \textit{bipartite graph} if and only if $\forall e \in E$, edge $e$ has exactly one end vertex in $U$ and the other end vertex in $V$. Let $W = U\cup V$. For $W' \subseteq W$, the \textit{induced subgraph} $G[W']$ is the subgraph over vertex set $W'$ with the edge set $\{\{u,v\}\in E | u, v\in W'\}$. An induced subgraph $G[W'] = (U',V',E')$ is a biclique if $\forall u \in U'$ and $\forall v \in V'$, we have $\{u, v\} \in E$. The \textit{open neighborhood} $N(v)$ of a vertex $v \in W$ is the set of vertices that are adjacent to $v$ in $G$. The \textit{degree} of a given vertex $v$ is denoted by $d(v)$, referring to the cardinality of $N(v)$. The \textit{closed neighborhood} of $v$ is denoted by $N[v]$, i.e., $N[v]=N(v)\cup \{v\}$. The open and closed neighborhoods of a set of vertices $W'\subseteq W$ are defined as $N(W')= \bigcup_{u\in W'} N(u) \textbackslash W' $ and $N[W'] = N(W') \cup W'$, respectively.  Let $W' \subseteq W$, we use $G - W'$ as the abbreviation for $G[W\textbackslash W']$ and for a vertex $v \in W$, let $G-v$ denote $G-\{v\}$. If $G-v$ has more connected components than $G$, then we call $v$ as a \textit{cut vertex}. Similarly, let $E'$ be a set of edges, then $G-E'$ denotes the graph $G' = (U,V, E\textbackslash E')$. For a graph $G = (U,V,E)$, denote $\overline{E} = \{\{u,v\}| u\in U \wedge v\in V \wedge \{u,v\} \notin E\}$ as the set of \textit{missing edges}. A pair of vertices $\{u,v\}$ is called a \textit{missing edge} if $\{u,v\}\in \overline{E}$. For two sets of vertices $X$ and $Y$, let $E(X,Y) $ be the set of edges between $X$ and $Y$, i.e., $E(X,Y)= \{\{u,v\}\ |\ u\in X \ \wedge\ v\in Y \ \wedge \ \{u,v\} \in E\}$. For a vertex set $X$, denote $E(X)$ as the abbreviation for $E(X,X)$. For a set of vertex $X'$ and a bipartite graph $H = (X,Y,E)$, denote the intersection between $X'$ and $H$ as the set of common vertices, i.e., $X' \cap H = (X'\cap X)\cup (X'\cap Y)$.

A problem is \textit{fixed-parameter tractable} (FPT) with respect to a certain parameter $k$, if there is an algorithm that decides the problem in $f(k)\cdot n^{O(1)}$ time. Here, $n$ denotes the size of the input and $f$ is a computable function. The framework of \textit{fixed-parameter tractability} was developed by Downy and Fellows[CITE].

\subsection{$s$-biplexes}
An $s$-biplex is a connected bipartite graph $G =(U,V, E)$ with $d(u) \geq |V| - s$ for all $u\in U$ and $d(v) \geq |U| - s$ for all $v\in V$. Note that a normal biclique is thus a $0$-biplex. A bipartite graph $G$ is called an \textit{$s$-biplex cluster graph} if all its connected components are $s$-biplexes. Therefore, $s$-BIPLEX EDITING is the special case of bicluster editing with $\Pi$ equal to ``$s$-biplex".

\subsection{Average-$s$-biplexes}
In general graphs, average-$s$-plex was proposed as a ``density measure" involved with the mean of the degrees of all the vertices in a given graph [cite]. In a bipartite graph, we define the \textit{average degree} as $\overline{d}_U=|E|/|U|$ and $\overline{d}_V=|E|/|V|$. A connected graph $G = (U,V,E)$ is thus an \textit{average-s-biplex} $\overline{d}_U\geq |V|-s$ and $\overline{d}_V\geq |U|-s$, with $1\leq s\leq \min\{|U|,|V|\}$. This density measure can be considered as a further relaxation of $s$-biplex, with no requirement on the \textit{minimum} degree. In this work, we show the proof of the NP-completeness of AVERAGE-$s$-BIPLEX EDITING, i.e., the $\Pi$-BICLUSTER EDITING with $\Pi$ equal to ``average-$s$-biplex". Afterwards, in order to show FPT, a reduction to a more general problem is conducted, followed by a polynomial-time kernelization procedure which produces a graph with at most $2k((s+1)(4k+6s)+1)$ vertices, which implies FPT for AVERAGE-$s$-BIPLEX EDITING.

\subsection{Defective Biclique}
The concept of \textit{defective clique} has been reported previously to be useful in biological network analysis [cite]. Theoretical study has also shown the NP-completeness and FPT of $s$-DEFECTIVE CLIQUE EDITING and DELETION [cite]. A connected bipartite graph $G = (U,V,E)$ is an $s$-defective biclique if $|E| \geq |U|\cdot |V| -s$. We prove that $s$-DEFECTIVE BICLIQUE EDITING is NP-complete. Then, the sizes of forbidden subgraphs of $s$-defective bicluster graphs are shown to be bounded by $(2s+2)$, which leads directly to the FPT of $s$-DEFECTIVE BICLIQUE EDITING problem with respect to the parameter $(s,k)$.

\section{s-biplexes}
We show the proof of NP-completeness of $s$-BIPLEX EDITING problem by a reduction from 3-EXACT-3-COVER problem. Then a further characterization of \textit{s}-biplexes is shown by bounding the sizes of \textit{forbidden induced subgraphs}. This conclusion can be used to design a branching strategy for $s$-BIPLEX EDITING problem and thus proves its FPT, with respect to the parameter $(s,k)$. The same proofs also apply on $s$-BIPLEX DELETION problem.


\begin{theorem}
For any constant $s\geq 0$, $s$-BIPLEX EDITING is NP-complete
\end{theorem}
\begin{proof}
If $s$=0, then the problem is equivalent to BICLUSTER EDITING and thus is NP-complete [CITE]. For any $s\geq 1$, we reduce the NP-complete 3-EXACT-3-COVER (3X3C) problem [CITE], where given a collection $\mathcal{C}$ of triplets (a set of 3 elements is called a triplet) from an element set $A=\{a_1,a_2,a_3,...,a_{3n}\}$ with $n$ as an integer and $n\geq 1$, such that, each element of $A$ is a member of at most 3 triplets, one asks to find out a sub-collection $\mathcal{I}\subseteq \mathcal{C}$ of size $n$ that covers $A$, i.e., every element of $A$ appears in some triplet in $\mathcal{I}$. The set $\mathcal{I}$ is called an ``exact cover".

We construct an $s$-BIPLEX EDITING instance as follows:

Let $m = (72+s)n $. A bipartite graph $G = (U,V,E)$ is then constructed, based on the following procedure: For each element in $A$, one corresponding vertex is created in $U$, and for each triplet $S\in \mathcal{C}$, a set of $m$ vertices is added to $U$. The same construction is performed to create vertices in $V$, that is:

(1) $U=U_1 \cup U_2$, $V=V_1 \cup V_2$,\\
(2) $U_1=\{u_1,u_2,...,u_{3n}\}$, $V_1=\{v_1,v_2,...,v_{3n}\}$,\\
(3) $U_2=\bigcup_{S\in \mathcal{C}} \{u_{S_1},u_{S_2},...,u_{S_m}\}$, $V_2=\bigcup_{S\in \mathcal{C}} \{v_{S_1},v_{S_2},...,v_{S_m}\}$.\\

The edge set $E$ in $G$ consists of 5 subsets: First, we connect every $u_i\in U_1$ to its corresponding $v_i\in V_1$, $1\leq i\leq 3n$. Second, for each triplet $S\in \mathcal{C}$, let $S = \{a_x,a_y,a_z\}$, $(1\leq x,y,z \leq 3n)$. We connect $u_i \in U_1$ and $v_j\in V_1$ for all $i,j \in \{x,y,z\}$ with $i\neq j$.  Third, between $U_2$ and $V_2$, for each $S\in \mathcal{C}$, denote $U_S^m = \{u_{S_1}, u_{S_2},,...,u_{S_m} \}$ and $V_S^m = \{v_{S_1},v_{S_2},...,v_{S_m}\}$. We connect $u_{S_i} \in U_S^m $ to $v_{S_j} \in V_S^m$ for all $1\leq i,j\leq m$. Finally, for each $S = \{a_x,a_y,a_z\} \in \mathcal{C}$, $(1\leq x,y,z \leq 3n)$, every $u_i \in U_1 (i \in \{x,y,z\})$ is connected to all vertices in $V_S^m \subseteq V_2$, and every $v_i \in V_1$ $(i \in \{x,y,z\})$ is connected to all vertices in $U_S^m \subseteq U_2$. These two sets of edges constitute the fourth part and the fifth part of the edge set $E$ in $G$. To be more precise:

(1) $ E=\bigcup_{i=1}^5 E_i$,\\
(2) $E_1=\{\{u_i,v_i\}| \ i=1,...,3n\}$,\\
(3) $E_2=\{\{u_i,v_j\}| \ \exists S = \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i,j \in \{x,y,z\} \ \wedge \  i\neq j\}$,\\
(4) $E_3=\{\{u_{S_i},v_{S_j} \} |\ \exists S \in \mathcal{C} \ \wedge \  u_{S_i} \in U_S^m \ \wedge \ v_{S_j} \in V_S^m \}$,\\
(5) $E_4=\{\{u_i,v_{S_j} \} | \ \exists S= \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i\in\{x,y,z\} \ \wedge \  v_{S_j} \in V_S^m \}$,\\
(6) $E_5=\{\{v_i,u_{S_j} \} | \ \exists S= \{a_x,a_y,a_z\} \in \mathcal{C} \ \wedge \  i\in\{x,y,z\} \ \wedge \ u_{S_j} \in U_S^m  \} $.

For each triplet set $S\in \mathcal{C}$, we denote:

(1) $U_S=\{u_x, u_y, u_z| \{a_x,a_y,a_z\} \in S \}$,\\
(2) $V_S=\{v_x, v_y, v_z| \{a_x,a_y,a_z\} \in S \}$,\\
(3) $W_S=U_S \cup V_S$,\\
(4) $U_S^m = \{u_{S_1}, ..., u_{S_m}\}$,\\
(5) $V_S^m = \{v_{S_1}, ..., v_{S_m}\}$,\\
(6) $W_S^m = U_S^m \cup V_S^m $.\\

Obviously, the construction can be carried out in polynomial time. Let $M=2m(3|\mathcal{C}|-3n)$ and $N=|E_2|-6n$. The parameter $k$ is equal to $M+N$.

``$\Rightarrow$" Let $\mathcal{I} \subseteq \mathcal{C}$ be an exact cover of $A$. Define:

(1) $F_1 = \{\{u_i,v_{S_j}\}|\  u_i \in U_1 \ \wedge \  v_{S_j} \in V_S^m \ \wedge\  \{u_i, v_{S_j} \} \in E \  \wedge \  S\notin \mathcal{I}  \}$,\\
(2) $F_2 = \{\{v_i,u_{S_j}\}|\  v_i \in V_1 \ \wedge \ u_{S_j} \in U_S^m \ \wedge \ \{u_i, v_{S_j} \} \in E  \ \wedge \  S\notin \mathcal{I}  \}$,\\
(3) $F_3 = E_2 \textbackslash \{\{u_i,v_j\}|\ \ S = \{a_x,a_y,a_z\}\in \mathcal{I} \ \wedge \ i,j \in \{x,y,z\} \ \wedge \  i\neq j\}.$

Let $F$ be the union of $F_1$, $F_2$ and $F_3$. Since in $\mathcal{I}$, each element must be contained in exactly one triplet, then in the graph $G-F$, for all vertices $u \in U_1\cup V_1$, $u$ is connected with exactly one $W_S^m$. Hence $G-F$ is a bicluster graph containing $2|\mathcal{C}|$ bicliques and clearly gives a solution to the $s$-BIPLEX EDITING instance.

Since $|\mathcal{I}| = n$, then $|\mathcal{C}|-n$ is equal to the number of ``surplus triplets", i.e., the triplets that are not in $\mathcal{I}$. Thus, we have $|F_1| = |F_2| = 3(|\mathcal{C}|-n)\cdot m = M/2$. Moreover, in $G-F$, we have $3n+6|\mathcal{I}| = 9n$ edges between $U_1$ and $V_1$, thus we can easily compute that $|F_3| = |E_1|+|E_2| - 9n = |E_2|-6n$. Denote $F$ as the set of edited edges, i.e., the set of deleted edges and inserted missing edges. We have $|F| = |F_1|+|F_2|+|F_3| = M+N$. 

``$\Leftarrow$" In the reverse direction, if there exists an optimal solution for the $s$-BIPLEX EDITING instance, let $F$ be the set of edited edges. We prove that $|F|\geq M+N$. By contradiction, assume $|F| < M+N$, we then find another edited edge set $F'$ for the optimal solution, such that $|F'| \leq |F|$ and $|F'| = M+N$. 

Let $F' = F_1\cup F_2 \cup F_3$ and thus $|F'| = M+N$. Clearly $F'$ gives a solution to the $s$-BIPLEX EDITING instance. Then it remains to prove $F'$ is optimal. Before we reach a contradiction of the assumption above, we first show the correctness of the following inequality: $|F'| < m(\frac{m+1}{6})$. 

In 3X3C, each element can be covered by at most 3 triplets, thus $|\mathcal{C}|\leq 3n$. Hence $M = 2m(3|\mathcal{C}| - 3n)\leq 2m(9n - 3n) \leq 12mn$. Consider $|E_2|$, $|E_2| = 9|\mathcal{C}| - 3|\mathcal{C}| = 6|\mathcal{C}| \leq 18n$. Thus $|F'| = |F_1|+|F_2|+|F_3| = M+N = 2m(3|\mathcal{C}|-3n)+|E_2|-6n \leq 12mn +18n - 6n  = 12mn +12n = 12m \cdot \frac{m}{72+s}+ 12 \cdot \frac{m}{72+s} \leq \frac{m^2}{6} +\frac{m}{6}= m(\frac{m+1}{6})$

Let $G'$ be the result graph of $G$ after all edge insertions and edge deletions are performed. We next prove the claim: For every $W_S$ and $W^m_S$, we can always find an $s$-biplex $B$ in the result graph $G'$, such that $W^m_S \subseteq B \subseteq (W^m_S \cup W_S)$.

We proceed with the proof in two steps: In the first step, we show that for each $W^m_S$, there is always an $s$-biplex $B$ in $G'$, such that $|B \cap W^m_S| \geq \frac{3}{2} m +3$. 

By contradiction, if there is no such $s$-biplex in $G'$. Let $\mathcal{B} = \{B_1, B_2, ..., B_l\}$ be the set of \textit{s}-biplexes in the optimal solution $G'$, such that $|B_i\cap W^m_S| \neq \emptyset$ for $1\leq i \leq l$. According to the assumption, we have $|B_i \cap W^m_S| \leq \frac{3}{2} m + 2$ for all $1\leq i \leq l$. Let $x_i = |B_i \cap U^m_S|$, $y_i = |B_i\cap V^m_S|$, $x_i+y_i \leq \frac{3}{2} m + 2$. Obviously, we have to delete all the edges between $W^m_S \cap B_i$ and $W^m_S - B_i$. Hence the number of edge deletions $C_D$ is at least:\newline
\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{i=1}^{l}(x_i(m-y_i)+y_i(m-x_i)) \\
& = \frac{1}{2} \sum\limits_{i=1}^{l} (m(x_i+y_i) - 2x_i y_i)\\
& \geq \frac{1}{2} \sum\limits_{i=1}^{l} (m(x_i+y_i)- \frac{1}{2}(x_i+y_i)^2)& \mbox{(*)} \\
& = \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i)(m- \frac{1}{2} (x_i+y_i))) \\
& \geq \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i)(m- \frac{1}{2} (\frac{3}{2}m+2)))&\mbox{(**)}\\
& = \frac{1}{2} \sum\limits_{i=1}^{l}((x_i+y_i) (\frac{1}{4}m-1)) \\
& = \frac{1}{2} (\frac{1}{4}m-1)\sum\limits_{i=1}^{l}(x_i+y_i) \\
& = m(\frac{1}{4}m-1) = \frac{1}{4}m^2-m &\mbox{(***)}
\end{align*}
The inequality (*) holds since for all integers $x_i>0$ and $y_i>0$, we have $x_iy_i \leq \frac{1}{4} (x_i+y_i)^2$. The inequality (**) is correct because we have  $(x_i+y_i)\leq \frac{3}{2} m +2 $. The equality (***) is correct since we have $\sum\limits_{i=1}^l (x_i+y_i) = |W_S^m| = |U_S^m|+|V_S^m| = 2m$. Thus we know that $|F| \geq \frac{1}{4}m^2 -2m$. Consider $|F| - |F'|$, we have:
\begin{align*}
|F| - |F'|& \geq \frac{1}{4}m^2 -m - m(\frac{m+1}{6})\\
&= \frac{m}{6}(\frac{m}{2}-7)
\end{align*}

In our construction, $m = (72+s)n$, thus $\frac{m}{6}(\frac{m}{2}-7) >0$. This contradicts with the assumption that $F$ is optimal. Thereby we have proved that there always exists an $s$-biplex $B$ in $G'$ with $|B \cap W^m_S| \geq \frac{3}{2} m +3$. For each $W_S^m$, denote $B_S$ as the $s$-biplex in the optimal solution such that $|B\cap W_S^m| \geq \frac{3}{2}m+3$. 

In the second step, we prove the claim that for each $W_S^m$, we have $W_S^m\subseteq B_S \subseteq (W^m_S \cup W_S)$. By contradiction, we assume there is one vertex $x\in W_S^m$, such that $x\notin B_S$. Without loss of generality, we assume $x\in U_s^m$. Since $0\leq |B_S \cap U_S^m| \leq m$, the intersection between $B_S$ and $V_S^m$ must be at least $\frac{3}{2}m+3 - m = \frac{m}{2} +3$, i.e., $|B_S \cap V_S^m|\geq \frac{1}{2}m+3$. Thus to include $x$ into $B_S$, we need at most: (1) Remove the edges between $V_s^m - B_S$ and $x$, and (2) remove the edges between $V_S$ and $x$. This gives us a cost $C_I \leq |V_S^m - B_S|+3\leq m - (\frac{m}{2} +3) +3 = \frac{m}{2}$. On the other hand, to remove $x$ from $B_S$, it requires at least to delete all the edges between $x$ and $V_S^m\cap B$, which gives a cost $C_D=|V_S^m \cap B_S | = |W_S^m \cap B_S| - |U_S^m \cap B_S| \geq \frac{3}{2}m +3 - m = \frac{m}{2} +3 \geq C_I$. Hence we know that it is always better to include $x$ as part of $B_S$ than to leave $x$ out.

The remaining part of the claim that $B_S \subseteq (W_S^m \cup W_S)$ is proved similarly by contradiction. Suppose there exists a vertex $y \in B_S$ and $y \notin (W_S^m \cup W_S)$. Without loss of generality, we assume $y \in U$. Denote $C_I$ as the cost of including $y$ as a part of $B_S$. Then we have to insert between $y$ and $V_S^m$ at least $(|V_S^m| - s)$ edges. $C_I \geq |V_S^m| - s = m-s$. Consider the cost $C_D$ of removing $y$ from $B_S$. $C_D$ is at most the number of edges between $y$ and $V_S$. Since $|V_S| = 3$, we have $C_D \leq 3 < C_I$, contradicting with the claim of optimal solution. Hence no vertex outside $(W_S \cup W_S^m)$ would end up in $B_S$ in any optimal solution.

Above we have proved that for each $W_S^m$, there is an $s$-biplex $B_S$ in the optimal solution, such that $W_S^m \subseteq B_S \subseteq (W_S^m \cup W_S)$. That leaves only to find out where the vertices in $W_S$ end up. Examine an element $u_i\in U_1$, such that its corresponding element in $A$, $a_i$, is a member of (at least) two subsets $S_1, S_2 \in \mathcal{C}$. In the proof above, we have already shown that $W_{S_1}^m$ and $W_{S_2}^m$ are contained in distinct $s$-biplexes in any optimal solution. Hence we have to delete the edges either between $u_i$ and $V_{S_1}^m$, between $u_i$ and $V_{S_2}^m$ or both. Obviously, if each $u_i$ only connects to one $V_{S}^m$, the total number of edge deletions is at least $3m(|\mathcal{C}| - n)$. For all such vertices in $V_1$, the same argument applies. Hence we have $|F\cap (E_3\cup E_4 \cup E_5)|\geq M$.

Besides, since for each $s$-biplex in $G'$, we have $B_S \subseteq (W_S^m \cup W_S)$, we know that in the optimal solution, every $u_i \in U_1$ is a neighbor of at most three vertices in $V_1$. Since $|U_1|=|V_1| = 3n$, thus there are at most $9n$ edges between $U_1$ and $V_1$ in the optimal solution. Thereby the edge deletions between $U_1$ and $V_1$ is at least $|F\cap (E_1 \cup E_2)| \geq |E_1|+|E_2|- 9n = |E_2| - 6n = N$.

In conclusion, we have the results that $|F\cap (E_3\cup E_4 \cup E_5)|\geq M$ and $|F\cap (E_1 \cup E_2)| \geq  N$. Hence $|F| \geq M+N$. This contradicts with the assumption that $|F|< |F'| = M+N$. Therefore, we know that $F' = F_1\cup F_2\cup F_3$ gives an optimal solution to $s$-BIPLEX EDITING instance. Finally, let $\mathcal{B}^*$ be a subset of  all $s$-biplexes in the optimal solution, such that $\forall B\in \mathcal{B}^*$, we have $B = W_S^m \cup W_S$. Then $\{S\in \mathcal{C}|B_S\in \mathcal{B}^*\}$ gives a cover to 3X3C instance.
\end{proof}

In the rest of this section, we describe a set of \textit{forbidden induced subgraphs} $\mathcal{G}_F$, that a graph $G$ is an $s$-biplex cluster if and only if $G$ does not contain any induced subgraphs in $\mathcal{G}_F$. If $s=0$, then we have an instance of BICLUSTER EDITING problem, and if $s\geq1$, the structures of forbidden induced subgraphs are much more complex and we are facing with the an exponentially increasing amount of different possibilities. To solve the problem, we show, in the following proofs, that the sizes of forbidden induced graphs are bounded by $O(s)$ vertices. Based on this characterization, a branching strategy of $s$-BIPLEX EDITING problem can be established.

We start with some preliminaries. A connected induced subgraph $H=(R,T,E')$ is \textit{minimal forbidden induced subgraph} if $H$ is not an $s$-biplex but every induced proper subgraph of $H$ is an $s$-biplex, i.e., for an arbitrary vertex $v$ in $H$, $H-v$ is an $s$-biplex. We denote a vertiex $v$ in $H$ as ``$forbidden$" if $v$ is incident to more than $s$ missing edges, i.e., $v$ does not meet the criteria for $s$-biplex. Any subset of vertices $R'$ is called ``\textit{forbidden subset}" if $R'$ contains at least 1 forbidden vertex. To show the upper-bound for minimal forbidden induced subgraphs in bipartite graphs, two distinct cases must be studied separately: (1) subgraph $H$ contains forbidden vertex (vertices) only in $R$ (or $T$), and (2) $H$ contains forbidden vertices in both $R$ and $T$. We first raise and prove 3 claims regarding the properties of a minimal forbidden induced subgraph. Next, as a summary, we show that every minimal forbidden induced subgraph of biplexes contains at most $(3s+3)$ vertices in both the two cases mentioned above, for all $s\geq 1$. 

\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph. Without loss of generality, let $R$ be a forbidden subset, then $\min\limits_{u\in R}\{d(u)\} = |T| - s -1$
\end{lemma}

\begin{proof}
By contradiction, suppose we have a vertex $u^* \in R$ with $d(u^*) \leq |T| -s -2$. Then we try to find a non-cut vertex $v \in H$. Such vertex must exist, since it is well known that in an arbitrary graph $G$, there are at least 2 non-cut vertices. Remove $v$ from $H$, consider the result graph $H-v$, we have 2 cases:

Case i: $v\in N(u^*)$. Then in $H-v$, $d_{H-v}(u^*) = d(u^*)-1 < |T|-s-2$, $u^*$ is still a forbidden vertex.

Case ii: $v\notin N(u^*)$. Then in $H- v$, $d_{H-v}(u^*) = d(u^*)\leq |T|-s-2$, $u^*$ is still a forbidden vertex.

In summary, either case gives another forbidden subgraph whose size is smaller than $H$, contradicting with $H$ is minimal
\end{proof}

\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph. If $H$ has forbidden vertices both in $R$ and $T$, then $H$ can only be a path of length $2s+2$, and only the two endpoints of the path are forbidden vertices.
\end{lemma}

\begin{proof}
First we prove the claim that $H$ contains no more than two forbidden vertices if $H$ has forbidden vertices both in $R$ and $T$. By contradiction, assume there are $>2$ forbidden vertices in $H$. Since we know that in any graphs, there are at least 2 non-cut vertices. Let $u,v$ be the 2 non-cut vertices. We have 6 cases regarding the locations of the 2 vertices:

Case i: $u,v$ are both forbidden vertices, and $u,v \in R$. Then we can remove $u$ without separating $H$. In the subgraph $H-u$, we have $d_{H-u}(v) = |T| -s-1$, hence is still forbidden, contradicting with minimal forbidden induced subgraph. If $u,v\in T$, same proof applies.

Case ii: $u,v$ are both non-forbidden vertices, and $u,v\in R$. Since $R$, $T$ are both forbidden subsets, there exists a forbidden vertex $w \in R$, such that $d(w) = |T|-s-1$. Remove $u$ from $H$. In the result subgraph $H-u$, $d_{H-u}(w) = |T|-s-1$ and hence is still forbidden. If $u,v\in T$, same proof applies.

Case iii: $u$ is a forbidden vertex, $v$ is a non-forbidden vertex and $u,v \in R$. Then just remove $v$ and $H-v$ is still forbidden.

Case iv: $u$ is a forbidden vertex in $R$, $v$ is a non-forbidden vertex in $T$. Since $R$, $T$ are both forbidden sub sets, there exists a vertex $w\in T$, such that $d(w) = |R|-s-1$. We remove $v$ from $T$, then $d_{H-v}(w) = |R|-s-1$, thus $H-v$ is still forbidden.

Case v: $u$ is a non-forbidden vertex in $U$, $v$ is a non-forbidden vertex in $V$. Based on a proof similar with Case iv, we can remove either $u$ or $v$, the result subgraph is still forbidden.

Case vi: $u$ is a forbidden vertex in $R$, $v$ is a forbidden vertex in $T$. Let $w$ be a forbidden vertex in $H$ and $w \neq u$, $w\neq v$. Without loss of generality, we assume $w\in R$. Then we can remove $u$ from $H$. In the result graph $H-v$, $d_{H-v}(w) = |T|-s-1$ and thus $H-v$ is still forbidden.

To summarize the six cases, since we have two non-cut vertices and at least three forbidden vertices with at least one forbidden vertex in $R$ and at least one in $T$, we can always find a forbidden vertex $x$ and a non-cut vertex $y$ in the same vertex set (in $R$ or in $T$). Clearly, removing $y$ does not affect the property of forbidden vertex of $x$ and thus the result subgraph $H-y$ is still a forbidden induced subgraph. This contradicts with the assumption. Hence we proved that if $H$ is a minimal forbidden induced subgraph with forbidden vertices in both $R$ and $T$, then $H$ cannot contain more than two forbidden vertices.

Next, we prove that $H$ can only be a path of $2s+2$ vertices. Let $u^*$, $v^*$ be the two forbidden vertices in $H$. Suppose $u^* \in R$ and $v^* \in T$, consider a third vertex $w^*$, $w^* \neq u^*$, $w^* \neq v^*$. Clearly, such vertex $w^*$ exists. If $w^*$ is a non-cut vertex. Then consider the subgraph $H-w^*$, if $w^*\in R$, in $H-w^*$, $u^*$ is still a forbidden vertex; if $w^* \in T$, then in $H-w^*$, $v^*$ is still a forbidden vertex. In either case, $H$ is not minimal. Therefore, we know that in $H$, all vertices other than $u^*$ and $v^*$ must be cut vertices. Thus in $H$, we have $|R|+|T|-2$ cut vertices. Obviously, $H$ can only be a path and $u^*$, $v^*$ can only be the two endpoints of the path in $R$ and $T$, since otherwise $H$ would contain a cycle. Since $d(u^*) = d(v^*) = 1$, we know $|R| =|T| = s+1$. The claim is proved.
\end{proof}

\begin{lemma}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph with forbidden vertices only in $R$. Let $R_0\subseteq R$ be the subset of all forbidden vertices, $R_1= R - R_0$. Let $T_0  = N(R_0)$ and $T_1 = T - T_0$. Then we have:
\begin{enumerate}
\item $\forall u \in R_1$, $u$ is a cut vertex.
\item $\forall v \in T_0$, $v$ is a cut vertex.
\item If $|R_0| >1$, then $\forall u \in R_0$, $u$ is a cut vertex.
\item Particularly, if $|T_0|>1$, for an arbitrary vertex $v^* \in T_0$ , let $\mathcal{H} = \{ H_1, H_2, ... ,H_l\}$ be the set of disjoint component after removing $v^*$, $l$ is an integer greater than $0$. Then for each $H_i =(X_i, Y_i, E_i)$, $1\leq i\leq l$, we have: $X_i\cap R_1 \neq \emptyset$. 
\item There exists at least 1 vertex $v\in T_1$ such that $d(v) = 1$. 
\end{enumerate}


\end{lemma}

\begin{proof}
For claim 1 and claim 2, the proof is simple: If any vertex $u\in R_1$ is a non-cut vertex, we can remove $u$ from $H$ without affecting the property of all vertices in $R_0$ of being a forbidden vertex, thus $H-u$ is still forbidden, contradicting with ``minimal". If any vertex $v\in T_0$ is a non-cut vertex, we can remove $v$ from $H$. In the result subgraph $H-v$, $min\{d_{H-v}(u)\} = |T|-s-2$, thus $H-v$ is still forbidden. For claim 3, when there is more than one forbidden vertex in $R_0$, all vertices in $R_0$ must be cut-vertex, otherwise we could remove any one of them and the result graph is still forbidden, based on a proof similar with that for claim 1 and 2. 

Next we prove claim 4. By contradiction, if there exists $X_i$, such that $X_i\cap R_1= \emptyset$. Without loss of generality, let $H_1 = (X_1,Y_1, E_1)$ be such a subgraph. Since $X_1 \cap R_1 = \emptyset$, clearly, we have $X_1\cap R_0\neq \emptyset$. Then we have two cases:

Case i. If $Y_1 = \emptyset$. Then we know that for $u_0\in X_1$, in the original subgraph $H$, $d(u_0) = 1$. Since $u_0$ is in $R_0$, we know that in the original subgraph $H$, $\forall u \in R_0$, we have $d(u) = 1$. Therefore, $\forall u \in R_0$, $u$ is a non-cut vertex. Hence we can only have $|R_0| = 1$, since otherwise $R_0$ would contain non-cut vertex and thus contradicts with claim 3. However, since $|R_0| = 1$, $d(u) = 1$ $(u\in R_0)$, then clearly we have $|T_0| = 1$, contradicting with $|T_0| >1$ in claim 4.

Case ii. If $Y_1 \neq \emptyset$. Then since $X_1 \cap R_0 \neq \emptyset$, we have $Y_1 \cap T_0 \neq \emptyset$. We already know that in subgraph $H_1$, there must be at least two non-cut vertices. Assume a vertex $v\in Y_1$ is a non-cut vertex. then in the original subgraph $H$, $v$ must be a non-cut vertex as well, contradicting with claim 2. Thus we know that there must be at least two vertices $u_1, u_2 \in X_1$, such that $u_1$ ad $u_2$ are non-cut vertices. Consider $u_1$ and $u_2$, we have three following properties:

(1) In the original subgraph $H$, $u_1$ and $u_2$ must be connected to $v^*$. This is obvious since otherwise $u_1$ and $u_2$ would be non-cut vertices in $H$ as well, contradicting with claim 3.\\
(2)$\forall x, y \in N(u_1)$, in $H_1$, there exists a path $P$ from $x$ to $y$ without passing $u_1$. This is true since otherwise $u_1$ would be a cut vertex in $H_1$.\\
(3)$\forall x\in N(u_1)$, in $H_1$, there exists a path $Q$ from $x$ to $u_2$ without passing $u_1$. This is also true since otherwise $u_1$ would be a cut vertex in $H_1$.

Based on the three properties above, consider in the original subgraph $H$, $\forall x,y\in N(u_1)$. If $x\neq v^*$, $y\neq v^*$, then we already know that there exists a path $P$ from $x$ to $y$ without passing $u_1$. If $x=v^*$, we can also find a path from $y$ to $v^*$ without passing $u_1$. This is true, because we already know that there exists a path $Q$ from $y$ to $u_2$, and in $H$, $u_2$ is connected to $v^*$, thus $Q' = Q \cup\{v^*\}$ is the path we are seeking. In summary, $\forall x,y \in N(u_1)$ in $H$, there exists a path from $x$ to $y$ without passing $u_1$. Thus $u_1$ is a non-cut vertex in $H$. Moreover, since $u_1 \in R_0$, this contradicting with claim 3.

Finally, we prove claim 5. By contradiction, if $\forall v \in T_1$, we have $d(v)>1$, then we consider 2 cases:

Case i: $|R_0| >1$. As proved above, $\forall u\in R_0$, $u$ is a cut vertex and hence $d(u)>1$. Besides, since all vertices in $T_0$, $R_1$ are cut vertices, the degree of them are greater than one. In summary, for all vertices $x$ in $H$, $d(x)>1$. To reach a contradiction, we proceed with a ``cycle-searching" procedure. Starting from an arbitrary vertex $x_0 \in R$, we can always find a cycle $C_0$ ($C_0$ is the set of vertices in the cycle, $x_0 \in C_0$). Consider an arbitrary vertex $x_1 \in (C_0\cap R)$, $x_1 \neq x_0$ (such $x_1$ with $x_1\neq x_0$ can always be found, since a cycle in bipartite subgraph $H$ contains at least two vertices in $R$ and two vertices in $T$), we can find another cycle $C_1$, starting from $x_1$. Then $C_1$ must satisfies one of the four following conditions: (1) $C_1$ starts from $x_1$ and overlaps with $C_0$ on more than one vertex, (2) $C_1$ does not start from $x_1$ ($x_1$ is not contained in the cycle) but $C_1$ overlaps with $C_0$, (3) $x_1$ is contained in $C_1$ and $C_1$ only overlaps with $C_0$ on $x_1$ and (4) $x_1$ is not contained in $C_1$ and $C_1$ is totally separated from $C_0$. More precisely:

(1) $x_1 \in C_1$ and $|C_1\cap C_0|>1$\\
(2) $x_1 \notin C_1$ and $|C_1\cap C_0|\geq 1$\\
(3) $x_1 \in C_1$ and $C_1 \cap C_0 = \{x_1\}$\\
(4) $x_1 \notin C_1$ and $C_1 \cap C_0 = \emptyset $

Note that if we cannot find any $C_1$ satisfying condition 3 or condition 4, then obviously $x_1$ is a non-cut vertex (all its neighbors can reach each other without passing $x_1$). This contradicts with $\forall x\in R$, $x$ is cut vertex. Hence there must exist at least one such $C_1$ satisfying condition 3 or 4. Then in such $C_1$, we pick up one vertex $x_2 \in (C_1 \cap R)$ and $x_2 \neq x_1$. Starting from $x_2$, we can find a new cycle $C_2$. Similarly, $C_2$ must satisfy one of the four conditions listed below:

(1) $x_2\in C_2$ and $|C_2\cap (C_0\cup C_1)| >1$\\
(2) $x_2\notin C_2$ and $|C_2 \cap (C_0 \cup C_1)| \geq 1$ \\
(3) $x_2\in C_2$ and $C_2 \cap (C_0\cup C_1) = \{x_2\}$\\
(4) $x_2\notin C_2$ and $C_2 \cap (C_0 \cup C_1) = \emptyset$

Based on the same reasoning, if we cannot find a $C_2$ satisfying condition 3 or condition 4, then we have $x_2$ a non-cut vertex. Thus at least one $C_2$ satisfying condition 3 or 4 must be found. Then we find another vertex $x_3 \in (C_2 \cap R)$, $x_3\neq x_2$ and start to search for another cycle. This step is repeated by searching cycle $C_3$, $C_4$, ..., and at round $i$, we can always find a cycle $C_i$, satisfying one of the four conditions below:

(1) $x_i \in C_i$ and $|C_i\cap \bigcup\limits_{j=0}^{i-1} C_j)| >1$\\
(2) $x_i \notin C_i$ and $|C_i \cap \bigcup\limits_{j=0}^{i-1} C_j|\geq 1$\\
(3) $x_i \in C_i$ and $C_i \cap \bigcup\limits_{j=0}^{i-1} C_j = \{x_i\}$\\
(4) $x_i \notin C_i$ and $C_i \cap \bigcup\limits_{j=0}^{i-1} C_j = \emptyset$

If we cannot find a $C_i$ satisfying condition 3 or 4, then $x_i$ is non-cut vertex. By this procedure of searching cycles, we could traverse the whole $H$. Since $H$ is a finite graph, such $C_i$ satisfying condition 3 or 4 cannot be always found. There must exist an integer $l >0$, such that in the round $l$, we cannot find any ``unvisited" vertex and thus no $C_l$ satisfying condition 3 or 4 is found. Hence $x_l\in R$ is non-cut vertex, contradicting with the claim proved above. Thus we have proved that there must be at least one vertex $u$ in $H$ with $d(u) =1$. Since there cannot be any vertex in $R_0$, $R_1$ and $T_0$ with degree equal to 1, such vertex must be in $T_1$.

Case ii: $|R_0| = 1$. Let $u_0$ be the vertex in $R_0$. If $u_0$ is a cut vertex, then the proof in Case i. still applies. If $u_0$ is a non-cut vertex, we are still able to reach a contradiction by the ``cycle-searching" procedure. Instead of starting from an arbitrary vertex in $R$, we start the procedure from $u_0\in R$ to search for $C_1$. Since every vertex in $H$ other than $u_0$ must have a degree of at least two, $H$ must contain cycles. Besides, in bipartite subgraph $H$, all cycles have at least two vertices in $R$. Hence in any round $i$, $i\geq 2$, cycle $C_i$ must contain one vertex $x$ and $x \neq u_0$ and $x$ must be a cut vertex. Thereby, we could always proceed with the ``cycle-searching" procedure, starting from such $x$ for a new round to find cycle $C_{i+1}$. Finally, when no cycle satisfying condition 3 or 4 could be found, we reach a contradiction. The claim is thus proved.
\end{proof}

\begin{theorem}
Let $H = (R,T,E')$ be a minimal forbidden induced subgraph with forbidden vertices only in $R$. Let $R_0\subseteq R$ be the subset of all forbidden vertices, $R_1= R - R_0$. Let $T_0  = N(R_0)$ and $T_1 = T- T_0$. Then we have $|R|+|T| \leq 3s+3$
\end{theorem}
\begin{proof}
Consider an arbitrary vertex $v^*\in T_0$. Since $v^*$ is a cut vertex, let $\mathcal{H} = \{H_1, H_2, ... H_r\}$, $r>1$, $H_i = (X_i, Y_i, E_i)$ be the set of disjoint connected components after removing $v^*$. Without loss of generality, let $\{H_1, H_2, ..., H_l\}$ be the subset of $\mathcal{H}$, $l \leq r$, such that $X_i \cap R_0 \neq \emptyset$, for all $1\leq i\leq l$. We have the following two cases:

Case i. If $l\geq 2$, we know there is at least two disjoint components that intersect with $R_0$. Hence consider $\forall u \in X_1$, $\forall v\in Y_j$ $(1< j \leq l)$, we have $\{uv\}\notin E'$, since otherwise $u$, $v$ will not be in different disjoint components. Similarly, we have $\{u'v'\}\notin E'$, for all $u'\in X_j$ $(1<j\leq l)$, and any $v'\in Y_1$. Thus, we have $|Y_1| \leq s+1$ and $\sum\limits_{j=2}^{l} |Y_j| \leq s+1$, since otherwise we would have a $u\in R$ incident to more than $s+1$ missing edges, contradicting with Lemma 1. Because the number of missing edges incident to any vertex in $R$ cannot be larger than $s+1$, we have $|Y_1|+|T_1| \leq s+1$ and $\sum\limits_{j=2}^{l}|Y_j|+|T_1| \leq s+1$. Thus we have $|T| = |Y_1|+\sum\limits_{j=2}^{l}|Y_j|+|T_1| \leq s+1+s+1= 2s+2$. Moreover, as we know $\min\limits_{w\in T} d(w) = 1$ and $T$ does not contain forbidden vertex, we have $|R| \leq s+1$, otherwise there would be forbidden vertex in $T$. Thus the total size of the forbidden induced subgraph $H$ is $|R| +|T| \leq 2s+2+s+1= 3s+3$.

Case ii. if $\forall v\in T_0$, we have $l=1$, i.e., for all $v\in T_0$, the removal of which will not separate $R_0$. For an arbitrary vertex $v^*$ in $T_0$, let $\mathcal{H} = \{H_1, H_2, ... H_r\}$, $H_i = (X_i, Y_i, E_i)$ be the disjoint connected components after removing $v^*$. Without loss of generality, let $R_0 \subseteq X_1$. Then we prove that we can find at least one $u^*$, $u^*\in (N(v^*)\cap R_1)$, such that $u^*\notin N(v')$ for all vertices in $T_0$ other than $v^*$  $(v'\in T_0$, $v'\neq v^*)$.  By contradiction, if $\forall u \in (N(v^*) \cap R_1)$, we can always find a $v' \in T_0$, $(v'\neq v^*)$, such that $u\in N(v')$, then we know $u \in N(Y_1)$ in $H_1$, since $v'\in Y_1$. Obviously, this is not possible since each $H_i$ is disjoint. We have proved that each vertex $v^*$ in $T_0$ has at least one ``unique" neighbor in $R_1$. Thus $|T_0| \leq |R_1| \leq s+1 - |R_0| \leq s$. Moreover, we have $|T_1| \leq s+1$, since otherwise there would exist a vertex in $R_0$ incident to more than $s+1$ missing edges. Then the total size of the forbidden induced subgraph $H$ is $|R|+|T| \leq s+1 +s +s+1 \leq 3s+2$. In summary, the claim is proved. \end{proof}



\section{average-\textit{s}-plexes}
In this section, we consider the AVERAGE-\textit{s}-BIPLEX EDITING problem, proving its NP-completeness and its FPT with respect to parameters $(s,k)$. To show its NP-hardness, a two-step reduction is demonstrated: First, we reduce a well-known NP-complete MAXIMUM BALANCED BICLIQUE (MBB) problem to the problem of EQUAL-SIZE BICLUSTER EDITING, afterwards, a reduction from EQUAL-SIZE BICLUSTER EDITING to AVERAGE-\textit{s}-BIPLEX EDITING is conducted. The EQUAL-SIZE BICLUSTER EDITING (ESBE) problem is defined as follows:


EQUAL-SIZE BICLUSTER EDITING (ESBE):\\
\begin{adjustwidth}{1cm}{1cm}
\textbf{Input}: An undirected bipartite graph $G=(U,V,E)$ and two integers $k,d \geq 0$.\\
\textbf{Question}: Can $G$ be transformed by editing at most $k$ edges into $d$ disjoint bicliques $\{C_1, C_2, C_3, ... C_d\}$, $C_i = (U_i,V_i,E_i)$, $1\leq i\leq d$, such that $|U_i| =|U_j|$ and $|V_i| = |V_j|$ for all $1\leq i,j\leq d$? 
\end{adjustwidth}
The edge deletion version of this problem requires only edge deletions.

\begin{theorem}
EQUAL-SIZE BICLUSTER EDITING is NP-complete
\end{theorem}

\begin{proof}
Obviously, the problem is in NP. Then the NP-hardness of the problem is shown by a reduction from MAXIMUM BALANCED BICLIQUE (MBB):

\begin{adjustwidth}{1cm}{1cm}
\textbf{Input}: An undirected bipartite graph $G=(U,V,E)$, and and integer $k\geq 0$\\
\textbf{Question}: Does there exist an induced biclique $C^* = (U_{C^*}, V_{C^*}, E_{C^*})$ in $G$, such that $|U_{C^*}| = |V_{C^*}| =k $  ?
\end{adjustwidth}

Given an MBB instance $G = (U,V,E)$ and a nonnegative integer $k$, we construct an EQUAL-SIZE BICLUSTER EDITING (ESBE) instance as follows:

(1) Add a set of components $\mathcal{A}$ to $G$, such that\\ $\mathcal{A} = \{A_1, A_2, ... , A_{|U|-k}\}$, $A_i = (U_{A_i}, V_{A_i}, E_{A_i})$, $1\leq i \leq |U|-k$. For each $A_i$, we have $|U_{A_i}| = k-1$, $|V_{A_i}| = k$. We first connect all vertices in $U_{A_i}$ to all vertices in $V_{A_i}$ for $1\leq i \leq |U|-k$, and then connect all the vertices in $U$ to all the vertices in $\bigcup \limits_{A_i \in \mathcal{A}} {V_{A_i}}$. \\
(2) Add a set of components $\mathcal{B}$ to $G$, such that \\ $\mathcal{B} = \{B_1, B_2, ... , B_{|V|-k}\}$, $B_j = (U_{B_j}, V_{B_j}, E_{B_j})$, $1\leq j \leq |V|-k$. For each $B_j$, we have $|U_{B_j}| = k$, $|V_{B_j}| = k-1$. We first connect all vertices in $U_{B_j}$ to all vertices in $V_{B_j}$ for $1\leq j \leq |V|-k$, and then connect all the vertices in $V$ to all the vertices in $\bigcup \limits_{B_j \in \mathcal{B}} {U_{B_j}}$.

Hence, we have the new graph for ESBE $G' = (U', V', E')$:

(1) $U' = \bigcup\limits_{A_i \in \mathcal{A}} U_{A_i} \cup  \bigcup\limits_{B_i \in \mathcal{B}} U_{B_i} \cup U$\\
(2) $V' = \bigcup\limits_{A_i \in \mathcal{A}} V_{A_i} \cup  \bigcup\limits_{B_i \in \mathcal{B}} V_{B_i} \cup V$\\
(3) $E' = E_1 \cup E_2\cup E_3\cup E_4 \cup E_5$\\
$E_1 = E$,\\
$E_2 = \{\{u,v\}\ |\  u\in U_{A_i} \ \ \wedge \ \  v \in V_{A_i} \}$,\\
$E_3 = \{\{u,v\}\ |\  u\in U_{B_i} \ \ \wedge \ \ v \in V_{B_i}\}$,\\
$E_4 = \{\{u,v\}\ |\  u\in U \ \ \wedge \ \ v \in V_{A_i}\ \ \wedge \ \ 1\leq i\leq |U|-k \}$\\
$E_5 = \{\{u,v\}\ |\  u\in V \ \ \wedge \ \ v \in U_{B_i}\ \ \wedge \ \ 1\leq i\leq |V|-k \}$

The sizes of $U'$ and $V'$ are: 

(1) $|U'| = k(|U| - k) + k(|V|-k)+k $\\
(2) $|V'| = k(|V| - k) + k(|U|-k)+k $. \\
(3) $|E'| = |E|+k(|U|-k)(|U|+k-1) + k(|V| - k)(|V| +k - 1)$

Let $k'$ and $d$ be the parameters of the new instance:


$k' = k(|U|-k)(|U| - 1)+k(|V|-k)(|V| - 1)+|E| - k^2$\\
and\\
$d  = |U|+|V|-2k+1$.


``$\Rightarrow$ " Suppose we have found a biclique $C^* = (U_{C^*}, V_{C^*}, E_{C^*})$ in $G$ with $|U_{C^*}| = |V_{C^*}| = k$. Then by the following steps, we can have a solution for the ESBE problem:

(1) For every vertex $u_i \in U\textbackslash U_{C^*} = \{u_1, u_2, ... u_{|U|-k} \}$, we delete the edges between $u_i$ and all vertices in $A_j$, $i\neq j$. For every vertex $u_i' \in U_{C^*} = \{u_{|U|-k+1}, u_{|U|-k+2}, ..., u_{|U|}\}$, we delete all the edges between $u_i'$ and all vertices in $\bigcup \limits_{A_i \in \mathcal{A}} {V_{A_i}}$. \\
(2) For every vertex $v_i \in V\textbackslash V_{C^*} = \{v_1, v_2, ... v_{|V|-k} \}$, we delete the edges between $v_i$ and all vertices in $B_j$, $i\neq j$. For every vertex $v_i' \in V_{C^*} = \{v_{|V|-k+1}, v_{|V|-k+2}, ..., v_{|V|}\}$, we delete all the edges between $v_i'$ and all vertices in $\bigcup \limits_{B_j \in \mathcal{B}} {U_{B_j}}$.\\
(3) Delete the edges between $C^*$ and $G - C^*$. 

Let $k_1' = k(|U|-k)(|U| - 1)$, $k_2' = k(|V|-k)(|V| - 1)$ and $k_3'= |E| - k^2$. Clearly, $k_1'+k_2'+k_3' = k'$. More specifically, step (1) requires $k(|U|-k)(|U| - k -1) + k^2(|U| - k) = k(|U| - k)(|U| -1) = k_1'$ edge deletions. Step (2) requires $k(|V| - k)(|V| - k -1)+k^2(|V|-k) = k(|V|-k)(|V|-1) = k_2'$ edge deletions. Step (3) requires $|E| - k^2 = k_3'$ edges deletions. Thus altogether the 3 steps above need $k_1'+k_2'+k_3' = k'$ edge deletions. Obviously the resulting graph contains $|U|+|V|-2k+1$ bicliques. This gives a solution to ESBE instance.

``$\Leftarrow$" Given the ESBE instance, we know $|U'| = |V'| = k(|U|+|V|-2k+1)$. First, we prove that each $A_i$ (or $B_i$) will end up in a separated biclique in the optimal solution. That is, let $\mathcal{D} = \mathcal{A}\cup \mathcal{B}$, for each $D_i \in \mathcal{D}$, in the optimal solution, there exists a biclique $C_i$ such that $D_i\subseteq C_i$ and $D_j\cap C_i = \emptyset $ for all $1\leq i\neq j \leq |U|+|V|-2k$. 

Denote $\mathcal{C} = \{C_1, C_2, ... , C_d\}$ as the $d$ bicliques in the optimal solution and let $C_i= (U_i, V_i, E_i)$. Clearly, the bicliques in $\mathcal{C}$ are $d$ equally-sized balanced bicliques, thus we have $|U_i| = |V_i| = |U'|/d = |U'|/(|U|+|V| + 2k +1) = k$. Thus, the total number of edges in the optimal solution is $dk^2$. Compute the difference between $|E'|$ and the number of edges in the optimal solution, we have:

\begin{align*}
|E'| - dk^2 & = |E|+k(|U|-k)(|U|+k-1) +\\
            & \ \ \ \  k(|V| - k)(|V| +k - 1) - dk^2\\
            & = k(|U| - k)(|U| +k-1 - k) + \\
            &\ \ \ \ k(|V| - k)(|V| +k-1 - k) + \\
            &\ \ \ \ |E| - k^2\\
            & = k'\\
\end{align*}

Since $|E'| - dk^2 = k'$, this indicates that only edge deletions are allowed, otherwise we would have to convert $G'$ into $d$ equally-sized bicliques with more than $k'$ edge modifications. To show that each $D_i$ ends up in a separated biclique, we first show that for every $D_i$, there is a biclique $C_i$ in the optimal solution, such that $D_i \subseteq C_i$. The proof is as follows:

For each $A_i$, we can always find a biclique $C_i$ such that $U_{A_i}\cap U_i \neq \emptyset$ in the optimal solution. Let $u_0 \in (U_{A_i} \cap U_i)$. First, we show that $\forall v \in V_{A_i}$, we have $v\in C_i$. By contradiction, if there exists a vertex $v_0 \in V_{A_i}$ and $v_0 \notin C_i$, since $|V_i| = k$, there must exists a $v_0' \in V_i$ such that $v_0' \notin V_{A_i}$. Then we have to insert at least an edge between $u_0$ and $v_0'$ and thus contradicts with no edge insertion proved above. Second, we prove that $\forall u_0'\in U_{A_i}$, $u_0' \neq u_0$, we have $u_0' \in C_i$. By contradiction, if $u_0' \in C_j$, $i\neq j$, then clearly, we have to insert the edges between $u_0'$ and $V_j$ thus contradicts with no edge insertion. The same proof applies on $B_i$ as well. Therefore, we have proved that, for every $D_i$, there exists a $C_i$ such that $D_i \subseteq C_i$. 

Next, we show that $C_i \cap D_j = \emptyset$ for all $i\neq j$. By contradiction, if there exists an integer $j$, such that $C_i \cap D_j \neq \emptyset$, $i\neq j$, then we have to insert edges in $C_i$ between $D_i$ and $D_j \cap C_i$. This contradicts with no edge insertion. Thereby, we have proved that every $D_i$ ends up in a separated biclique, $1\leq i \leq |U|+|V|- 2k$.

Finally, we prove an optimal solution to ESBE will give a solution to MBB. Without loss of generality, we assume $A_1 \subseteq C_1$. Since $|U_1| = k$ and $|U_{A_1}| = k-1$, clearly there is one vertex $u_1\in C_1$ but $u_1 \notin A_1$. We next discuss where this $u_1$ comes from. As proved above, $u_1$ cannot be from $A_i$, $i>1$ or  any $B_j$, $1\leq j \leq |V|-k$. Thus we have $u_1\in U$. Therefore, for every $A_i$, $1\leq i\leq |U|-k$, there exists one vertex $u_i$ in $U$, such that $u_i$ ends up in the same biclique with $A_i$. Similarly, we can show that for every $B_i$, $1\leq i \leq |V|-k$, there exists one vertex $v_i$ in $V$, such that $v_i$ ends up in the same biclique with $B_i$. That leaves us $|U| - (|U| - k) = k$ vertices in $U$ and $|V| - (|V| - k) = k$ in $V$. If these $2k$ vertices cannot form a balanced biclique in $G'$, then we have to insert edges between them. This would lead to more than $k'$ edge modifications and thus contradicts with the assumption. Therefore, if we have a solution to ESBE instance, we must be able to find a biclique with $k$ vertices in each vertex set in $G$, which gives a solution to the MBB instance.\end{proof}


\begin{theorem}
For every constant $s\geq 1$, AVERAGE-$s$-BIPLEX EDITING is NP-complete
\end{theorem}

\begin{proof}
We reduce ESBE to AVERAGE-\textit{s}-BIPLEX EDITING. First, given an ESBE instance $G=(U,V,E )$, with $k$ as the parameter of maximum number of edge modifications and $d$ as the number of bicliques in the solution, we can safely assume that $|U| = |V|$, an AVERAGE-{s}-BIPLEX EDITING instance $G' = (U',V',E')$ is constructed by adding $d$ components to each of $U$ and $V$, respectively: 

$U' = U \cup U_1\cup U_2 \cup ... \cup U_d$,\\
$V' = V \cup V_1 \cup V_2 \cup ... \cup V_d$.

Let $l =|U|/d $. Each of $U_i$ and $V_i$ contains $d^4l^4s^4$ vertices, i.e.: 

$|U_i| = |V_i| = d^4l^4s^4$.

We denote $W_i = U_i\cup V_i$. For each $U_i$, we divide the vertices in $U_i$ into $d^4l^4s^3$ vertex groups: $U_i = U_i^1 \cup U_i^2 \cup ... \cup U_i^{d^4l^4s^3}$. $|U_i^j| = |U_i^{j'}|$ and $U_i^j \cap U_i^{j'} = \emptyset$ for all $j \neq j'$. Hence we have $|U_i^{j}| = s$ for all $1\leq j\leq d^4l^4s^3$. For each $V_i$, we divide them in the same way. 

$U_i = \bigcup \limits_{j=1} ^{d^4l^4s^3} U_i^{j}$ and $V_i = \bigcup \limits_{j=1} ^{d^4l^4s^3} V_i^{j}$.

Then we connect: (1) all vertices in $ U_i$ to all vertices in $V$, and (2) all vertices in $ U_i$ to all vertices in $U$. Next, inside each $W_i$, we connect all vertices in $U_i^j$ to all vertices in $\bigcup_{j\neq j'} V_{i}^{j'}$, leaving the vertex pairs $\{u,v\}$ with $u\in U_i^j, v \in V_i^j)$ unconnected. Finally, within each $W_i$, we further remove $s\cdot l$ arbitrary edges, which leaves $|U_i|\cdot |V_i| - s\cdot |U_i| - sl = d^8l^8s^8 - s(d^4l^4s^4 +l)$ edges in each $W_i$. The new parameter $k' = k+ 2(d-1)d^5l^5s^4$. Obviously, $G'$ is not an average-$s$-biplex cluster graph and edge modifications are required. Note here we can assume that $1 \leq s < d\cdot l$.

``$\Rightarrow$" If we have a solution for ESBE, i.e., a group of $d$ bicliques with equal size $l$ which costs at most $k$ modifications. Let $\mathcal{B} = \{B_1, B_2, ...,B_d\}$ be the set of $d$ bicliques in the solution. Then a solution for AVERAGE-$s$-BIPLEX EDITING is constructed by disconnecting $B_i$ with all constructed components $W_j$, $1\leq i\neq j\leq d$. Thus each $B_i$ is only connected to $W_i$, $1\leq i\leq d$. This asks for $2(d-1)d^5l^5s^4$ edge deletions. Denote $C_i = B_i \cup W_i$. Since $|C_i \cap U'| = |C_i \cap V'|$, then it is sufficient just to consider the average degree of the vertices in $|C_i \cap U'|$. The average degree in $C_i$ is:

\begin{align*}
\overline{d_{C_i}} = \frac{(|E(U_i, V_i)|+|E(U_i,B_i)|+ |E(V_i,B_i)|+|E(B_i)|)}{(|U_i|+|U' \cap B_i|)}
\end{align*}

Here, $E(U_i,V_i)$ refers to the edges between $U_i$ and $V_i$; $E(U_i,B_i)$ and $E(V_i,B_i)$ refer to the edges between $B_i$ and $U_i$, $B_i$ and $V_i$, respectively; $E(B_i)$  is the set of edges within the biclique $B_i$. According to the construction of $G'$, $|E(U_i,V_i)| = d^8l^8s^8 - s(d^4l^4s^4+l)$, $|E(U_i,B_i)|= |E(V_i,B_i)| = s^4d^5l^5$. Since $B_i$ is biclique, we have $|E(B_i)| = l^2$. Hence the result of the average degree is:

\begin{align*}
\overline{d_{C_i}} & = \frac{(|E(U_i, V_i)|+|E(U_i,B_i)|+ |E(V_i,B_i)|+|E(B_i)|)}{(|U_i|+|U' \cap B_i|)}\\
&= \frac{d^8l^8s^8 - s(d^4l^4s^4+l)+2d^4l^5s^4+l^2}{l+d^4l^4s^4}\\
&= \frac{(d^4l^4s^4 +l)^2 - s(d^4l^4s^4+l)}{d^4l^4s^4+l}\\
&= d^4l^4s^4 - s\\
&= |V_i|+| V' \cap B_i| - s
\end{align*}

This average degree satisfies the average-$s$-biplex. This will give a solution to AVERAGE-$s$-BIPLEX EDITING instance.

``$\Leftarrow$". We firstly prove that for each $W_i$ there is an average-$s$-biplex $D_i$ in the optimal solution, such that $W_i \subseteq D_i$, $1\leq i \leq d$ and $W_j \cap  D_i = \emptyset$ for $1\leq j\leq d$, $i\neq j$. In order to prove this claim, we proceed in several steps. First, we prove that, for each $W_i$, there exists an average-$s$-biplex $D_i$ and $|D_i \cap W_i| \geq d^4l^4s^4$.

By contradiction, if there does not exist such an average-$s$-biplex in the optimal solution. Denote $\mathcal{D} = \{D_1, D_2, ...,D_r\}$ as the set of average-$s$-biplexes in the optimal solution, $r\geq 1$. Then we have $\forall D_j \in \mathcal{D}$, $|W_i \cap D_i| < d^4l^4s^4$, $1\leq j \leq r$, $1\leq i\leq d$. Specifically, consider $W_1$, without loss of generality, let $\mathcal{D}' = \{D_1, D_2, ...,D_t\}$, $1\leq t\leq r$ be the set of average-$s$-biplexes in the optimal solution that intersect with $W_1$. Let $X_i = U_1 \cap D_i$, and $Y_i = V_1 \cap D_i$, $1\leq i \leq t$. Thus we have to delete the edges between different average-$s$-biplexes. The corresponding number of edge deletions $C_D$ is:
\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{i=1}^{t} (|X_i|(|V_1|-|Y_i|) + |Y_i|(|U_1|-|X_i|)) - s(d^4l^4s^4+l)\\
    & = \frac{1}{2} \sum\limits_{i=1}^{t} (|X_i|(d^4l^4s^4-|Y_i|) + |Y_i|(d^4l^4s^4-|X_i|)) \\
    & - s(d^4l^4s^4+l)\\
    & = \frac{1}{2}\sum\limits_{i=1}^{t} (d^4l^4s^4(|X_i|+|Y_i|) - 2|X_i||Y_i|) - s(d^4l^4s^4+l)\\
    & \geq \frac{1}{2}\sum\limits_{i=1}^{t} (d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}(|X_i|+|Y_i|)^2)\\
    & - s(d^4l^4s^4+l) \ \ \ \  (*)\\
    & \geq \frac{1}{2}\sum\limits_{i=1}^{t}(d^4l^4s^4(|X_i|+|Y_i| - \frac{1}{2}|X_i| - \frac{1}{2}|Y_i|))\\
    &- s(d^4l^4s^4+l) \ \ \ \ (**)\\
    & = d^4l^4s^4\cdot \frac{1}{2}\sum\limits_{i=1}^{t}(\frac{1}{2}(|X_i|+|Y_i|))- s(d^4l^4s^4+l)\\
    & = \frac{1}{2}d^8l^8s^8 - s(d^4l^4s^4 +l)\ \ \ \  (***)
\end{align*}

Inequality (*) holds because for an arbitrary pair of integers $(a,b)$ that are greater than 0, we have $ab \leq \frac{1}{4} (a+b)^2$. Inequality (**) holds because we assume $|X_i|+|Y_i| < d^4l^4s^4$ for all $i$, thus $d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}(|X_i|+|Y_i|)^2 < d^4l^4s^4(|X_i|+|Y_i|) - \frac{1}{2}\cdot  d^4l^4s^4 (|X_i|+|Y_i|)$. Equality (***) holds since we have $\sum\limits_{j=1}^{t}(|X_i|+|Y_i|) = |U_1|+|V_1| = 2d^4l^4s^4$. Obviously, when $d\geq 2$, $l\geq 1$, $s\geq 1$, we have $C_D > k'$, contradicting with the assumption that $D$ is a solution.

Denote $D_1$ as the average-$s$-biplex such that $|D_1 \cap W_1| \geq d^4l^4s^4$. Let $X_1 = D_1 \cap U_1$ and $Y_1 = D_1 \cap V_1$. Next, we prove that $|X_1|\geq \frac{1}{3}d^4l^4s^4$ and $|Y_1| \geq \frac{1}{3}d^4l^4s^4$. 

By contradiction, assume $|X_1| < \frac{1}{3}d^4l^4s^4$. Then we have to delete all the edges between $W_1\cap D_1$ and $W_1 - D_1$. The cost for edge deletions $C_D$ is lower-bounded by:
\begin{align*}
C_D & \geq |X_1|(|V_1|-|Y_1|) + |Y_1|(|U_1|-|X_1|) - s(d^4l^4s^4+l)\\
& \geq d^4l^4s^4(|X_1|+|Y_1|) - \frac{1}{2}(|X_1|+|Y_1|)^2 - s(d^4l^4s^4 +1)\\
& \geq d^4l^4s^4 \cdot \frac{4}{3} d^4l^4s^4 - \frac{1}{2} \cdot \frac{16}{9} d^8l^8s^8 - s(d^4l^4s^4 +1)\ \  (*)\\
& = \frac{4}{9}d^8l^8s^8 - s(d^4l^4s^4 +1) \geq k'
\end{align*}
Inequality (*) holds, since $d^4l^4s^4(|X_1|+|Y_1|) - \frac{1}{2}(|X_1|+|Y_1|)^2$ reaches the maximum value within the range of $0\leq |X_1| \leq \frac{1}{3} d^4l^4s^4$ and $\frac{2}{3}d^4l^4s^4 \leq |Y_1| \leq d^4l^4s^4$, when $|X_1| = \frac{1}{3} d^4l^4s^4$, $|Y_1| = d^4l^4s^4$. Thus we have a cost of edge deletion greater than $k'$, contradicting with the assumption. Hence it is proved that $|X_1|,|Y_1| \geq \frac{1}{3}d^4l^4s^4$.

Next, consider $D_1$, let $P = (\bigcup \limits_{j=2}^{d} U_j \cap D_1)$ and $Q = (\bigcup \limits_{j=2}^{d}V_j \cap D_1)$. That is, $P$ and $Q$ together represent the set of vertices in $D_1$ and in all other $W_j$s, $1<j\leq d$. Next, we prove: $|P| \leq 4s$ and $|Q| \leq 4s$.

Since the vertices in $P$ and $Q$ belong to other $W_j$s, $1<j\leq d$, thus to include them in $D_1$, we have to insert a certain number of edges between $P$, $Q$ and $W_1$. Denote $X_1^* = U \cap D_1$ and $Y_1^* = V\cap D_1$. We compare the cost of insertions to include these vertices into $D_1$ and the cost of deletions to remove them out from $D_1$. Note in the following computation, we compute only the average degree for the vertices in $U'\cap W_1$, since the average degree for $V'\cap W_1$ gives the same result. To meet the condition of average degree, the insertion cost $C_I$ is lower-bounded as follows:
\begin{align*}
C_I & \geq (|D_1\cap U'|-s)|D_1 \cap V'| - \max\{|E(D_1\cap U', D_1\cap V')|\}\\
& \geq ((|Q|+|Y_1|+|Y_1^*|)-s)(|P|+|X_1|+|X_1^*|) - \\
& \ \ \ \ ((|Q|+|Y_1|+|Y_1^*|)(|P|+|X_1|+|X_1^*|) - |P||Y_1| - |Q||X_1|)\ \ \ (*) \\ 
& \geq (|Y_1|-s)|P|+(|Q|-s)|X_1|-s|X_i^*| 
\end{align*}

Inequality (*) holds because to lower-bound $C_I$, we use the maximum value of $|E(D_1\cap U', D_1\cap V')|$. However, for edge deletions, we only need: 
\begin{align*}
C_D & = |P||Y_1^*| + |Q||X_1^*|
\end{align*}

Thus, we have:
\begin{align*}
C_I-C_D & \geq (|Y_1| - |Y_1^*|-s)|P| + (|Q|-s)(|X_1|-|X_1^*|) - \\
& 2s|X_1^*|\\
\end{align*}

By contradiction, we assume $|P| \geq 4s$, then:
\begin{align*}
C_I-C_D & \geq 4s|Y_1| - 4s^2 - 4s|Y_1^*| + (|Q|-s)(|X_1| -|X_1^*|) -\\
& \ \ \ \ 2s|X_1^*| \\
& \geq 4s|Y_1| - 4s^2 - 4s|Y_1^*| - s|X_1| - 2s|X_1^*|\ \ \ (*)\\
& \geq 4s\cdot \frac{1}{3} d^4l^4s^4 - 4s^2 - 4s|Y_1^*| - s\cdot d^4l^4s^4 \\
& \ \ \ -2s\cdot dl\ \ (**) \\
& \geq \frac{4}{3}d^4l^4s^5 - 4s^2 - 4sdl -d^4l^4s^5 - 2sdl \\
& \geq \frac{1}{3}d^4l^4s^5 - 4s^2 - 5sdl >0
\end{align*}
In inequality (*), we have $(|Q|-s)(|X_1| -|X_1^*|) = -s|X_1| + |Q|(|X_1| - |X_1^*|) + s|X_1^*|\geq - s|X_1|$. In inequality (**), we have $|Y_1| \geq \frac{1}{3} d^4l^4s^4$, $|X_1|\leq d^4l^4s^4$, $|X_i^*|\leq dl$ and $|Y_i^*|\leq dl$. This $C_I-C_D$ is clearly greater than $0$, indicating it is better to remove all vertices in $P$ and $Q$. Thus we know that $|P|\geq 4s$, we could remove all vertices in $P$ and $Q$ out from $D_1$, contradicting with $\mathcal{D}$ is an optimal solution.

By contradiction, if $|Q| \geq 4s$, then:
\begin{align*}
C_I - C_D & \geq (|Y_1| - |Y_1^*|-s)|P|+ 3s\cdot(|X_1| -|X_1^*|) - 2s|X_1^*|\\
 & \geq 3s\cdot(|X_1| -|X_1^*|) - 2s|X_1^*|\\
 & \geq 3s( \frac{1}{3}d^4l^4s^4 - dl) - 2sdl \ \ \ (*)\\
 & = d^4l^4s^5 - 5sdl >0
\end{align*}

Inequality (*) is correct since $|X_1| \geq \frac{1}{3}d^4l^4s^4$ and $|X_1^*| \leq dl$. Thus we know that $|Q|$ cannot be greater than $4s$. Thus we proved that both $|P|$, $|Q|$ are smaller than $4s$, otherwise it would need less cost to delete these vertices from $D_1$ than to include them in $D_1$. 

Now based on the claims above, we prove that $\forall u\in W_1$, we have $u\in D_1$. We prove this by comparing the cost of including an arbitrary vertex $u \in W_1$ into $D_1$ ($C_I$) and the cost of removing $u$ from $D_1$ ($C_D$). Without loss of generality, we assume $u\in U_1$. For $u$, the cost of removing $u$ from $D_1$ is at least the edges between $u$ and $Y_1$:
\begin{align*}
C_D & \geq |Y_1| - s - sl \\
    & \geq \frac{1}{3}d^4l^4s^4 - s- sl
\end{align*} 

To include the $u$ into $D_1$, we need to delete the edges between $u$ and the vertices outside $D_1$, insert all the missing edges incident to $u$ and insert the missing edges between $u$ and $Q$:
\begin{align*}
C_I & \leq |Y_1^*|+s+sl+4s\\
    & \leq dl+5s+sl
\end{align*} 

Clearly, $C_D>C_I$, then we conclude for each $u \in W_1$, we have $u \in D_1$ in the optimal solution, i.e., $W_1\subseteq D_1$. Next we prove that for each vertex $v \in \bigcup\limits_{1\leq i\leq d} W_i \textbackslash W_1$, we have $v \notin D_1$ in any optimal solution. In order to show this claim, we compare the cost of including $v$ into $D_1$ ($C_I$) and the cost of deleting $v$ from $D_1$ ($C_D$). Without loss of generality, we assume $v \in U'$. To include $v$ in $D_1$, we have to keep the average degree satisfying the criteria:
\begin{align*}
C_I & \geq (1+|X_1|+|X_1^*|+|P|)(|Y_1|+|Y_1^*|+|Q|) \\
	& - s(|Y_1|+|Y_1^*|+|P|) \\
    & -|Y_1^*| + |X_1||Y_1^*| - |X_1^*||Y_1| - |X_1^*||Y_1^*|\\
    & - |X_1||Y_1| + s(|Y_1|+l) \\
    & - |P|(|Y_1|+|Y_1^*|+|Q|)-|Q|(|X_1|+1+|X_1^*|)\\
    & = |Y_1| + sl -s|V_1^*| - 4s\\
    & \geq d^4l^4s^4+sl-sdl - 4s
\end{align*}

And to remove $v$ from $D_1$, we just need to delete at most the edges between $v$ and $Y_1^*$ and the edges between $v$ and $Q$. 
\begin{align*}
C_D &\leq dl+4s
\end{align*}

Obviously, we have $C_I > C_D$, thus it is better to remove every $u\notin W_1$ from $D_1$. In summary, we have proved that there are $d$ disjoint components in the optimal solution, each of which contains one $W_i$. For each vertex $u \in G$, in the optimal solution $u$ must be connected to one of the $d$ components. This asks for $k'-k = 2(d-1)d^5l^5s^4$ edge deletions. 

Finally, we show that for all $D_i$, we have $|D_i \cap U| = |D_i \cap V| = l$. First, we prove that $|D_i \cap U| \geq l$ and $|D_i \cap V|\geq l$, for all $1\leq i \leq d$. By contradiction, if $|D_i \cap U|<l$, then the average degree of the vertices in $D_i\cap U'$ is upper-bounded by:

\begin{align*}
\overline{d_{D_i\cap U'}} & \leq \frac{|D_i\cap V'|\cdot |D_i\cap U'| - s(d^4l^4s^4+l)}{|D_i\cap U'|}\\
                          &  = |D_i \cap V'| - \frac{s(d^4l^4s^4 +l)}{|D_i \cap U'|}\\
                          & < |D_i \cap V'| - s \ \ \ \ (*)
\end{align*}

Inequality (*) holds since $|D_i\cap U|<l$ and thus we have $|D_i \cap U'|\leq (d^4l^4s^4 +l)$. This contradicts with optimal solution. Similarly, we can prove that $|D_i \cap V|\geq l$ for all $1\leq i \leq d$. Since $|U| = |V| = dl$ and there are $d$ bicliques in the optimal solution, we know that $|D_i\cap U| = |D_i\cap V| = l$. Moreover, in the optimal solution, the induced subgraph $G'[D_i \cap (U\cup V)]$ must form a biclique, otherwise $D_i$ would not be an average-$s$-biplex. Thus, this requires that $G$ be transformed into $d$ equally-sized balanced bicliques within $k$ edge modifications. Therefore, in summary, in the optimal solution, $G$ must be converted into $d$ disjoint equal-size bicliques and thus gives a solution to ESBE instance.\end{proof}


We present a kernalization procedure for AVERAGE-$s$-BIPLEX EDITING with the parameter $(s,k)$. In order to show this, first we reduce the problem into an integer-weighted version and afterwards we describe three reduction rules that can be carried out within polynomial time.

We introduce two types of weights to describe the weighted version of AVERAGE-$s$-BIPLEX EDITING: Vertex weights and edge weights, inspired by the idea of the reduction of the weighted version of CLUSTER EDITING, i.e. for any pair of vertices that cannot be separated by $k$ edge modifications, we merge them into one ``multi-vertex". Obviously, for all vertices merged, they end up in the same average-$s$-biplex in all optimal solutions.

We denote the vertex weight as $\sigma(u)$ which keeps track of the number of vertices merged into $u$. The vertex weight of a set of vertices $S$ is defined as: $\sigma(S) = \sum\limits_{v\in S} \sigma(v)$. Moreover, let $\delta(u)$ be the subset of vertices $\{u_1, u_2, ..., u_r\}$, $r\geq 1$ that merged into $u$, i.e., $\sigma(u) = |\delta(u)|$. The edge weight, $\omega(u,v)$, is defined between two arbitrary entities (The concept ``entity" represents vertices, multi-vertices and sets of vertices), storing the number of edges between them. The degree of a vertex $u$ is defined as: $d'(u) = \omega(u,N(u))$. Thus, for a bipartite graph $G= (U,V,E)$, the average degree of the vertices in $U$ is defined as:
\begin{align*}
\overline{d_{U}} = \frac{\omega(U,V)}{\sigma(U)}
\end{align*}
Hence a bipartite graph $G=(U,V,E)$ is a weighted average-$s$-biplex, if $\overline{d(u)}_{u\in U} \geq \sigma(V) - s$ and $\overline{d(v)}_{v\in V} \geq \sigma(U) - s$. The weighted version of the problem can be defined as:

\begin{adjustwidth}{1cm}{1cm}
\textbf{Input:} A graph $G=(U,V,E)$, with vertex weight $\sigma(u)$ as a function: 
\begin{equation*}
\sigma (u):
\left \{ 
\begin{array}{lll}
U&\rightarrow &[\ 1,|U|\ ]\\
V&\rightarrow &[\ 1,|V|\ ]
\end{array}
\right.
\end{equation*}
and edge weight $\omega(u,v)$ as a function:
\begin{align*}
\omega(u,v): E \ \ \rightarrow \ \ [\ 1,|U||V|\ ]
\end{align*}
and a nonnegative integer $k$.

\textbf{Question:} With edge modifications whose total weight is at most $k$, can $G$ be edited into a weighted average-$s$-biplex cluster graph?
\end{adjustwidth}

Note that if we set $\sigma(u)\coloneqq 1$, $\delta(u) \coloneqq \{u\}$ and for each $\{\{u,v\}\in E$, $\omega(u,v) \coloneqq 1$, an instance of AVERAGE-$s$-BIPLEX EDITING can be easily reduced to an instance of WEIGHTED AVERAGE-$s$-BIPLEX EDITING. In this reduction, parameters $k$ and $s$ are not changed. 

The following three reduction rules were designed for WEIGHTED AVERAGE-$s$-BIPLEX EDITING, which leads to a problem kernel with no more than $2k((s+1)(4k+6s)+1)$ vertices.

\begin{itemize}
\item \textbf{Rule 1.} Remove all connected components in $G$ that are already weighted average-$s$-biplexes.
\end{itemize}
The correctness of Rule 1. is trivial.

\begin{itemize}
\item \textbf{Rule 2.} For two vertex $u,v \in U$ or $u,v \in V$, let $S(u,v) \coloneqq N(u)\cap N(v)$. If \\$\min\{\omega(u, S(u,v)), \omega(v,S(u,v))\}>k$, then we merge $u$ and $v$, by replacing $u$ and $v$ with a new vertex $v'$, such that $v'$ satisfies:\\
- $\sigma(v') = \sigma(u) + \sigma(v)$\\
- $\omega(v',x) = \omega(u,x) + \omega(v,x)$ for every $x$ with $\{u,x\}\in E$, $\{v,x\}\in E$
\end{itemize}

\begin{lemma}
\textbf{Rule 2.} is correct
\end{lemma}
\begin{proof}
Obviously, to separate $u$ and $v$, we must not allow $u$ and $v$ to have any common neighbors. Thus at least $d = \min\{\omega(u, S(u,v)), \omega(v,S(u,v))\}$ deletions are required. If $d>k$, then we cannot afford the cost of deletions. Hence $u$ and $v$ must end up in the same average-$s$-biplex.
\end{proof}


The function of Rule 2. is to merge (or replace) the vertices that we cannot afford separating. Based on the same idea, we consider another scenario: If a vertex $u$ has a large set of neighbors that are only linked to $u$ but no other vertex, then we cannot possibly deleted the edges between $u$ and all its ``unique" neighbors. Let $N^*(u) \subseteq N(u)$ be a set of vertices such that $\forall v\in N^*(u)$, $v$ satisfies:

(1) $N(v) = \{u\}$\\
(2) $\sigma(v) = 1$

Rule 3. is then presented to reduce the size of $N^*(u)$:

\begin{itemize}
\item \textbf{Rule 3} For each $u\in G$, if $|N^*(u)| >k$, then we replace $N^*(u)$ with a subset of vertex containing $(k+1)$ vertices: $\{v_0,v_1, v_2...,v_k\}$, such that $\omega(u,v_0) = \omega(u,N^*(u))-k$ and $\omega(u,v_i) = 1$ for all $1\leq i \leq k$.
\end{itemize}

\begin{lemma}
Rule 3 is correct
\end{lemma}

\begin{proof}
Without loss of generality, let $L \subseteq N^*(u)$ be the subset of $N^*(u)$ that end up in the same average-$s$-biplex  as  $u$, and $M = N^*(u) \textbackslash L$. Thus we have $|M| \leq k$, since otherwise we would have to delete more than $k$ edges between $M$ and $u$. Thus $|L| \geq |N^*(u)| - k$. Note that the vertices in $M$ and $L$ are ``\textit{interchangeable}", i.e. for any vertex $m\in M$ and $l\in L$, we can exchange the locations of $m$ and $l$, by putting $m$ in $L$ and $l$ in $M$. Such location-exchange requires no further edge modification. Suppose in an optimal solution, $m\in M$ is connected to a set of vertices $Z$. Obviously, $u\notin Z$. Thus to reconnect $m$ to $u$, we have to re-insert the deleted edge between $u$ and $m$, and remove all the inserted edges between $m$ and $Z$. That saves $|Z|+1$ edge modifications. Next, to move $l$ out and connect $l$ with $Z$, we have to delete the edge between $l$ and $u$, and insert the edges between $l$ and $Z$. This procedure requires $|Z| +1$ edge modifications. Therefore, $M$ and $L$ are interchangeable. Let $N^*(u) = \{v_1, v_2, ..., v_r\}$, $r\geq k+1$. We can claim that the vertex set $L' = \{v_{k+1}, ..., v_r\}$ is a subset of $L$ and all vertices in $L'$ end up in the same average-$s$-biplex with $u$. This claim is true because we cannot afford deleting the edges between $u$ and more than $k$ vertices in $N^*(u)$. Since all vertices in $L'$ end up in the same average-$s$-biplex, we can merge them together. Thus, Rule 3. is correct.
\end{proof}

\begin{theorem}
(WEIGHTED) AVERAGE-$s$-BIPLEX EDITING is fixed-parameter tractable with respect to parameter $(s,k)$ and admits a kernel of at most $2k((s+1)(4k+6s)+1)$ vertices.
\end{theorem}

\begin{proof}
Let $G$ be a connected component in the optimal solution after applying the reduction rules exhaustively. Since we have removed all existing average-$s$-biplexes, $G$ must be incident to edge modifications. Thus there exist at most $2k$ connected components. Let $G=(U,V,E)$ and without loss of generality, we assume $|U|\leq |V|$. First we prove $|U| \leq 4k+6s$.

By contradiction, if $|U|>4k+6s$, then obviously we have $|V| > 4k+6s$. Let $u^*$ be the vertex in $U$ that has the largest degree. Obviously, $d'(u^*)\geq \sigma(V)-s\geq |V|-s$. We distinguish in two cases:

Case i: $\sigma(u^*) > \frac{1}{2} \sigma(U) > 2k+3s$. Note that for all edges incident to $u^*$, we can have at most one edge with weight larger than $k$. This is true because by contradiction, if we have $v_1$, $v_2 \in V$ and $\omega(u^*,v_1)>k$, $\omega(u^*, v_2)>k$, then we could merge $v_1$ and $v_2$ by Rule 2. Since $u$ has at least $|V| -s $ neighbors, we can compute the number of missing edges $m_e$ incident to $u$ as:
\begin{align*}
m_e& \geq (|V|-s-1)(\sigma(u^*)-k) \ \ (*)\\
   & > (4k+5s-1)\cdot \sigma(u^*)/2 \\
   & > 4s \cdot \sigma(u^*)/2\\
   & \geq 4s\cdot \sigma(U)/4\\
   & =s \cdot \sigma(U)
\end{align*}

Thus the average degree of $U$ is :
\begin{align*}
\overline{d(U)} &< \frac{\sigma(U)\cdot\sigma(V) -s \cdot \sigma(U) }{\sigma(U)} \\
 & =\sigma(V) - s
\end{align*}

Inequality (*) holds because there can be at most one edge incident to $u^*$ with edge weight larger than $k$ and then for the rest of the neighbors (at least $|V|-s-1$ vertices), each of them is incident to at least $(\sigma(u^*)-k)$ missing edges. Hence $G$ does not satisfy average-$s$-biplex, we have a contradiction. 

Case ii: $\sigma(u^*) \leq \frac{1}{2}\sigma(U)$. Then we first prove that there must exist another vertex $u'$, such that $\omega(u',V) \geq |V|-2s$. Suppose there does not exist such a vertex, then we compute the number of missing edges $m_e$:
\begin{align*}
m_e &> (\sigma(V) - (|V| - 2s ))(\sigma(U)- \sigma(u^*)) \ \ (*)\\
    &> 2s\cdot \sigma(U)/2\\
    &> s\cdot \sigma(U)
\end{align*} 

Thus the average degree of $U$ is smaller than $\sigma(V)-s$. Inequality (*) holds because the degrees of the vertices other than $u^*$ in $U$ are all smaller than $|V|-2s$. Then for each of such vertices, there are at least $\sigma(V)-(|V|-2s)$ missing edges incident to it. Hence we proved that there must be a vertex $u'$ with $d'(u') \geq |V|-2s$. Consider $u^*$ and $u'$, the number of shared neighbors between them is at least:
\begin{align*}
&\geq |V|-s+|V|-2s - |V|\\
&\geq |V|-3s\\
&\geq 4k+3s >k
\end{align*}

This contradicts with Rule 2., since we can merge $u^*$ and $u'$ together. So far, we have proved that $|U| \leq 4k+6s$. Next we show $|V|$ cannot be larger than $(4k+6s)\cdot s+k$ vertices. 

By contradiction, assume $|V| > (4k+6s)\cdot s +k$. Since $G$ is already an average-$s$-biplex, there can be at most $\sigma(U)\cdot s\leq s(4k+6s)$ missing edges in $G$. Hence in $V$, there can be at most $s(4k+6s)$ vertices incident to missing edge(s). By $|V|>(4k+6s)\cdot s +k$, there are at least $k$ vertices that are connected to all vertices in $U$. If $|U| \geq 2$, then for every pair of vertices in $U$, they share more than $k$ common neighbors in $V$, contradicting with Rule 2. That leaves the only case of $|U|=1$. Let $U = \{u\}$, We consider two sub-cases:

Case i: If $\sigma(u) > k$, then there are at least $k$ vertices in $v\in V$, such that $\omega(v,U) > k$. This contradicts with Rule 2.

Case ii: If  $\sigma(u) \leq k$, then we prove the claim that: $\forall v\in V$, $\sigma(v) = 1$. By contradiction, assume if there exists a vertex $v'$ such that $\sigma(v')>1$. Then consider two vertices $v_1$, $v_2 \in \delta(v')$, $\sigma(v_1) = 1$, $\sigma(v_2) = 1$. We must have the common neighbors of $v_1$ and $v_2$ be a subset of $\delta(u)$, i.e., $S(v_1,v_2) \subseteq \delta(u)$. Thus $|S(v_1,v_2)|<k$. Then we have $\omega( v_1, S(v_1,v_2)) < k$ and $\omega(v_2, S(v_1, v_2)) < k$. Thus $v_1$ and $v_2$ would not be merged, contradicting with Rule 2. Since we proved that $\forall v\in V$, $\sigma(v) = 1$, then $|V|$ cannot be bigger than $k+1$; otherwise we could apply Rule 3. to reduce it. 

In summary, we proved that $|U|\leq 4k+6s$ and $|V| \leq (4k+6s)\cdot s +k$. Then the total number of vertices in $G$ is at most $2k(((s+1)(4k+6s))+k)$.\end{proof}

\section{Defective Bicliques}
\begin{theorem}
For any every $s\leq0$, $s$-DEFECTIVE BICLUSTER EDITING is NP-complete 
\end{theorem}

\begin{proof}
For $s=0$, the problem is equivalent to BICLUSTER EDITING problem and thus is NP-complete. For any $s$>1, we give a reduction from BICLUSTER EDITING. The same construction also works for $s$-DEFECTIVE BICLUSTER DELETION.

Given a BICLUSTER EDITING instance: a bipartite graph $G= (U,V,E)$ and a nonnegative integer $k$, we construct a new graph $G'$ by adding $n$ components ($n = |U|+|V|$) to $G$: $\{W_1,W_2,..., W_n\}$. $W_i =(U_i, V_i, E_i)$, $|U_i| = |V_i| = n^4+s$. We connect all vertices $u \in U_i$ to all vertices $v\in V$, all vertices $v\in V_i$ to all vertices $u\in U$. Inside each $W_i$, we have $|E_i| = |U_i||V_i| - s$ edges, i.e. insert all but $s$ edges. The parameter $k'$ is equal to $k+n(n-1)(n^4+s)$.

``$\Rightarrow$" Let ${B_1,B_2,...,B_l}$ be the $l$ $(l<n)$ bicliques in the optimal solution for the BICLUSTER EDITING instance. Then for all $v \in B_i$ $(1\leq i \leq l)$, remove all the edges between $v$ and $W_j$ for all $i\neq j$, $1\leq j \leq n$. Denote $G^*$ as the result graph from $G'$ after the edge deletions. Clearly, $G^*$ is an $s$-defective bicluster. Moreover, the total number of edge modifications is equal to the edge modification used for bicluster editing in $G$ plus the edge deletions afterwards: $k' = k +n(n-1)(n^4+s)$, satisfying the edge modification upper-bound. Hence we have a solution for $s$-DEFECTIVE BICLUSTER EDITING instance.

``$\Leftarrow$" Let $\{D_1, D_2,..., D_r\}$, $r\geq 1$ be the connected components in an optimal solution of $G'$. Denote the resulting graph as $G^*$. Clearly, each $D_i$, $1\leq i\leq r$, is an $s$-defective biclique.

In order to prove solution for $s$-DEFECTIVE BICLUSTER EDITING is also optimal solution for BICLUSTER EDITING, we first show for every $W_i$ with $1\leq i \leq n$, there is a $D_i$ such that $W_i \subseteq D_i$ and $D_i \cap W_j = \emptyset$ for all $1\leq j\neq i \leq n$. By contradiction, we assume this is not the case. Then there must exist at least one $W_i$, we assume it to be $W_1$, such that there is no $D_i$ completely containing $W_1$ in $G^*$. Without loss of generality, we assume that $\mathcal{D} = \{D_1, D_2, ..., D_t\}$, $1\leq t\leq r$, is the set of components that intersect with $W_1$. We then claim that there exists a $D_j$, such that $|D_j \cap W_1| \geq (n^4+s)$, $1\leq j\leq t$. Denote $X_j = D_j \cap U_1$ and $Y_j = D_j \cap V_1$. If we have $|D_j \cap W_1| < (n^4+s)$, for all $1\leq j \leq t$, then the edges between $W_1 \cap D_j$  and $W_1 \textbackslash D_j $ must be deleted. Thus the number of edge deletions $C_D$ that we need:
\begin{align*}
C_D & \geq \frac{1}{2} \sum\limits_{j=1}^t (|X_j|(|V_1| - |Y_j|) + |Y_j| (|U_1| - |X_j|)) - s\\
    & = \frac{1}{2} \sum\limits_{j=1}^t ((n^4+s)(|X_j+|Y_j|) - 2|X_j||Y_j|) - s\\
    & \geq \frac{1}{2} \sum\limits_{j=1}^t ((n^4+s)(|X_j+|Y_j|) - \frac{1}{2}(|X_j|+|Y_j|)^2) -s\\
    & > \frac{1}{2} \sum\limits_{j=1}^t((n^4+s)(|X_j|+|Y_j| - \frac{1}{2}|X_j| - \frac{1}{2}|Y_j|)) - s\ \  (*)\\
    & = \frac{1}{4}(n^4+s) \sum\limits_{j=1}^t(|X_j|+|Y_j|) - s\\
    & = \frac{1}{4}(n^4+s)^2 - s \geq k'
\end{align*}

Inequality (*) is correct since we assume $|D_j \cap W_1| < n^4+s$, for all $1\leq j \leq t$. Thus we have $\frac{1}{2}(|X_j|+|Y_j|)^2 < \frac{1}{2}(n^4+s)(|X_j|+|Y_j|)$. The above inequality shows that if we have $|D_j \cap W_1|< n^4+s$ for all $1\leq j \leq t$, then we need more than $k'$ edge modifications, contradicting with the assumption of optimal solution. Thus we know that, for each $W_i$, there exists a $D_j$ such that $|W_i \cap D_j| \geq (n^4+s)$. Consider $W_1$. Let $D_1$ be the component such that $|W_1 \cap D_1| \geq (n^4+s)$. We next prove that $|X_1| > \frac{1}{3}(n^4+s)$ and $|Y_1| > \frac{1}{3}(n^4+s)$. 

By contradiction, without loss of generality, we assume $|X_1| \leq \frac{1}{3} (n^4+s)$. Then we compute the cost of deletions within $W_1$:
\begin{align*}
C_D & \geq |X_1|(|V_1| - |Y_1|) + |Y_1|(|U_1| - |X_1|) - s\\
    &  = (n^4+s) (|X_1| + |Y_1|) - 2|X_1||Y_1| - s\\
    &  \geq (n^4+s)(|X_1| + |Y_1|) - \frac{1}{2}(|X_1| + |Y_1|)^2 - s\\
    & \geq \frac{4}{3}(n^4+s)^2 - \frac{8}{9}(n^4+s)^2 - s \ \  (*)\\
    & = \frac{4}{9} (n^4+s)^2 - s \geq k'\\
\end{align*}

In the inequality (*), we compute the minimum value for $(n^4+s)(|X_1| + |Y_1|) - \frac{1}{2}(|X_1| + |Y_1|)^2 $, within the range of $0\leq |X_1| \leq \frac{1}{3}(n^4+s)$, $\frac{2}{3}(n^4+s) \leq |Y_1| \leq n^4+s$. The result shows that we must have more than $k'$ edge modifications if $|X_1|$ or $|Y_1|$ is at most $\frac{1}{3} (n^4+s)$, thus contradicting with the assumption of optimal solution.

Next, based on the claims proved above, we show that: (1) $W_1\subseteq D_1$ and (2) for all $j$ that $j\neq 1$, we have $W_j \cap D_1 = \emptyset$, $1<j\leq n$. First, for each $u \in W_j$ $1<j\leq n $, we prove $u \notin D_1$. We compute the $C_I$ as the cost of including $u$ into $D_1$ and the cost $C_D$ as the cost of removing $u$ from $D_1$. Without loss of generality, we assume $u \in U_j$:

\begin{align*}
C_I & \geq  |D_1| - s \\
   & \geq \frac{1}{3}(n^4+s) - s\\
C_D & \leq |V| \leq n\\
\end{align*}

Obviously, $C_I > C_D$, thus it is better to remove such $u$ from $D_1$. Similarly, for each $v\in W_1$ we compute the cost  $C_I$ of including it into $D_1$ (to delete edges connecting $v$ and the vertices outside $D_1$), and the cost $C_D$ of removing $v$ out from $D_1$. Without loss of generality, we assume $v\in U_1$:
\begin{align*}
C_I & \leq |V| \leq n\\
C_D & \geq |D_1| -s \\
 & \geq \frac{1}{3}(n^4+s) - s\\
\end{align*}
Clearly, it is better to include these vertices as part of $D_1$. So far, we have proved that for each $W_i$, there is one $D_i$ such that $W_i \subseteq D_i$. Hence in the optimal solution, we have at least $n$ components, which requires $k'-k$ deletions. If $G$ cannot be edited within $k$ edge modifications into disjoint set of bicliques, there must be more than $s$ missing edges in some component in the result graph $G^*$. Thus we must be able to modify $G$ into a set of disjoint bicliques, in order to have an optimal solution for $s$-DEFECTIVE BICLUSTER EDITING. In conclusion, if we have an optimal solution for $s$-DEFECTIVE BICLUSTER EDITING, then the induced subgraph of the result graph $G^*[U\cup V]$ gives a solution to BICLUSTER EDITING. \end{proof}

Next, we show the FPT of $s$-DEFECTIVE BICLUSTER EDITING problem by proving that for every $s\geq1$, all minimal forbidden induced subgraphs contain at most $2s+2$ vertices and hence we are able to find a minimal forbidden subgraph in polynomial time.

\begin{lemma}
For $s\geq 1$, every minimal forbidden induced subgraph of $s$-defective biclique contains at most $2s+2$ vertices. Given a connected graph that is not an $s$-defective biclique, a minimal forbidden induced subgraph can be found in $O((|U|+|V|)\cdot |E|)$ time.
\end{lemma}

\begin{proof}
Denote $H = (R,T,E')$ as a forbidden induced subgraph of $s$-defective biclique. We prove the claim by contradiction: Suppose all forbidden induced subgraph contain more than $2s+2$ vertices. We distinguish 2 cases:

Case i. There exists a cut vertex in $H$. Suppose $u^*\in R$ is a cut vertex. Then we remove $u^*$ and obtain a set of disjoint connected components $\mathcal{H} = \{H_1,H_2,...,H_l\}$, $H_i =(R_i,T_i,E_i) $. Thus, we have the number of missing edges $e_m$ is at least:
\begin{align*}
e_m &\geq \frac{1}{2}\sum\limits _{i=1}^{l}(|R_i|(|T|-|T_i|)+|T_i|(|R|-1-|R_i|))\\
    & = \frac{1}{2}\sum\limits _{i=1}^{l} |R_i||T| + \frac{1}{2}\sum\limits _{i=1}^{l} |T_i|(|R|-1) -
        \sum\limits _{i=1}^{l} |R_i||T_i|\\
    & =(|R| - 1)|T| - (|R_1||T_1| +\sum\limits _{i=2}^{l}|R_i||T_i|)\\
    & \geq (|R|-1)|T| - (|R_1||T_1| + (\sum\limits _{i=2}^{l}|R_i|)(\sum\limits _{i=2}^{l}|T_i|))\ \  (*)\\
    &  = (|R|-1)|T| - (|R_1||T_1| + (|R|-1-|R_1|)(|T|-|T_1|)) \\
    &  = |T_1|(|R| -1 - |R_1|)+|R_1|(|T| - |T_1|) \\
    & \geq |R|+|T| -3 \ \ \ (**)
\end{align*}

Inequality (*) holds because for any integer $a_1,b_1,a_2,b_2 >0$, we have $a_1\cdot b_1 + a_2\cdot b_2 \leq (a_1+b_1)(a_2+b_2)$. Inequality (**) is the minimum value of the function $f(|T_1|,|R_1|) = |T_1|(|R| -1 - |R_1|)+|R_1|(|T| - |T_1|)$, with $1\leq |R_1| \leq |R|-1$ and $1\leq |T_1| \leq |T|$. Thus, we have $e_m\geq s+1$, when $|R|+|T| = s+4$ and $H$ is a forbidden induced subgraph. However, $s+4 < 2s+2$ for all $s\geq 1$, thus contradicts with the assumption.

Case ii. If there is no cut vertex in $H$, then we know that $\forall v \in H$, $v$ must be incident to missing edge(s), otherwise we can just remove $v$ from $H$ without changing the forbidden subgraph property.  Let $n = |U|+|V|$, $m_0$ be the minimum ``anti-degree" ( ``anti-degree" is the number of missing edges incident to a given vertex) in $H$ and $m_t$ be the total number of missing edges in $H$. Hence we have the inequality group:

\begin{equation*}
\left\{
\begin{array}{rl}
\frac{1}{2}\cdot n \cdot m_0 &\leq m_t \ \ (1) \\
m_t-m_0&\leq s \ \ \ \ (2)
\end{array}
\right.
\end{equation*}

Inequality (1) holds because each vertex is incident to at least $m_0$ missing edges and altogether we have no more than $m_t$ missing edges. Inequality (2) holds because $H$ is a minimal forbidden subgraph and the removal of any vertex $v$ will decrease the total missing edges by at least $m_0$. Since $H$ is minimal, $\forall u \in H$, $H-u$ is not forbidden and thus has no more than $s$ missing edges. Solving the inequality group, we have:
\begin{align*}
n&\leq \frac{2s+2m_0}{m_0} =\frac{2}{m_0}s+2 \leq 2s+2
\end{align*}

Thus if $n>2s+2$, then at least one inequality above is not satisfied and hence $H$ is not minimal forbidden induced subgraph. To locate a minimal forbidden induced subgraph in $H$, we first check $H$ is an $s$-defective biclique. If not, we check for each $v \in H$, the subgraph $H- v$. If $H-v$ is still forbidden, then we remove $v$ from $H$. This procedure terminates in $O(|E|)$ time. Thus to find a minimal forbidden induced subgraph takes at most $O((|U|+|V|)|E|)$ time.\end{proof}


\section{Outlook}
We point out some further directions of this research topic. For all the three problems, further algorithmic improvements are necessary: For $s$-BIPLEX and $s$-DEFECTIVE BICLUSTER EDITING, a more elegant and efficient problem kernel is needed, and for average-$s$-BIPLEX EDITING, an efficient branching strategy other than brute-force is beneficial to be applied on the reduced problem kernel. Moreover, in many practical applications, for example in computational biology, high-quality heuristic algorithms should always be taken into account. Finally, it is also interesting to consider other meaningful density measurements and study their classical and parameterized complexity.

\end{document}
